algorithm - O(n) の最長共通部分列

Question

O(n) 時間で最長サブシーケンスの長さを見つけるための可能なアルゴリズムはありますか? O(nlogn)について知っています。

Answer 1

いいえ、O(n) の複雑さで結果が得られる LCS のアルゴリズムはありません。O(nlgn) は、この問題の最高のパフォーマンスです。