2
複数の文字列（k> 2）の中で最も長い共通部分列問題がNP-Hardである理由を理解するのは難しいことです。私は長さl1、l2の2つの文字列のLCS問題はO（l1 * l2）時間で解決できることを知っています。私が質問したのは、なぜなら、一度に2つの文字列のLCSを見つけることができないからです。例えば：なぜ複数のストリングで最も長い共通部分シーケンスがNP-Hardですか？
LCS（abcd、ad、abc）= LCS（LCS（abcd、ad）、abc）= LCS（ad、このアルゴリズムは、k個の文字列に対してO（k * Max_length^2）を要する。なぜこれは間違っていますか？
あなたの最初の等号が間違っている：LCS（eeeabcd、eeead、abc）！= LCS（LCS（eeeabcd、eeead）、abc）例えば – user1470500
LCS（eeeabcd、eeead）= eeead、LCS ？ – Kapil