找到O（NlogN）時間中最長的公共子序列

Question

有沒有找到O（NlogN）時間中兩個序列的最長公共子序列的方法？

我在某處讀到有一種方法可以使用二進制搜索來實現此目的。

我知道需要O（N ）時間的dp方法。

Answer 1

的dynamic programming approach，這是爲O（n 2 ）是完全通用的。對於某些其他情況下，也有低複雜度的算法：

• 對於一個固定的字母大小（不與ñ增長），有其帶來的時間縮短到澳Method of Four Russians（ n/log n）（參見here）。

• 請參閱here另一個進一步優化的案例。

Answer 2

兩個序列之間最長的公共子序列基本上是n-squared。

Masek and Patterson (1980)使用所謂的「Four Russians」技術對n平方/ logn進行了小的改進。

在大多數情況下，由這種複雜方法引入的額外複雜性並不合理的小收益。出於實際目的，您可以將n平方方法視爲典型應用中的合理最優方案。

Answer 3

對於一般情況，O（N^2）動態規劃算法是最好的。但是，在一些特殊情況下存在更好的算法。

1. 字母大小爲界

這是一個很常見的情況。由某些字母（例如英文）組成的字母在這一類別中。對於這種情況，O（N * M）算法可以通過method of four Russians進行優化以獲得O（N^2/logN）。我不知道如何，你可以搜索它。

兩個序列由不同元件

一個例子的問題是 「考慮兩個數字排列，從1至N，發現他們的LCS」。這個可以在O（N * logN）中解決。
設序列爲A和B.
定義序列C.C [i]是A中的B [i]的索引（A [C [i]] = B [i]）
A B是C的longest increasing subsequence。

Answer 4

假設Exponential Time Hypothesis（它比P更嚴格，但仍被普遍認爲是真實的），對於任何肯定都不可能在時間O（N^{2-eps}常數eps，參見Karl Bringmann和Marvin Kunnemann的"Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping"（可在arXiv上預印）。

粗略地說，這意味着這個問題的一般情況不能比O（N^2/logN）更好地解決，所以如果你想要更快的算法，你必須考慮附加約束（一些屬性的字符串）或尋找近似的解決方案。