最長公共子串行是否存在低於 O n 2 的演算法？

1樓：陳晨

若字符集為常數，則可低於O(MN)

設字符集為C, 將動態規劃中n*n的矩陣拆分（n/t）^2個t＊t的小矩陣,其中t為1/2*log以c為底n，在預處理中小矩陣有c^2t種，每個小矩陣需要t^2時間計算，所以預處理需要o(n(logn)^2)，這樣每個可能的小矩陣的結果都已經計算完

最後針對n＊n大矩陣中的每個t＊t小矩陣填入返回值（由於小矩陣的返回值僅與它上面和左面邊上的值有關，因此檢查每個小矩陣的時候僅需要輸入上面和左面邊上的值，也只需要返回下面後右面邊上的值，這四條邊都是O(t），因此檢查乙個小矩陣也需要O(t）)

因為總共需要檢查（n/t）^2個小矩陣,檢查乙個小矩陣需要O(t）,最後得到右下角的值就需要（n/t）^2＊t=(n^2)/t = O((n^2)/logn)，小於O(MN)

2樓：

似乎沒聽說過嚴格小於 O(n^2) 的演算法，但是存在一般情況下 O(n log n) 的演算法。

對於 A，B 兩個串，將 A 中每個字元替換成在 B 中間出現的位置的逆序列，例如原串為

A="abacd"

B="cabbab"

字元 'a' 在 B 中出現的位置為 2, 5，字元 'b' 在 B 中出現的位置為 3, 4, 6，字元 'c' 出現的位置為 1，字元 'd' 沒有出現。那麼 A 序列將被替換成為

(5, 2), (6, 4, 3), (5, 2), (1), ()

每乙個括號代表原來的 A、B 兩串相同字元的匹配，如下圖：

但是匹配必須是遞增的，也就是每個括號裡選乙個數，選出的數必須遞增。將括號裡的數反序排列是為了方便限制「每個括號裡選乙個數」的條件。

這是 LCS（最長公共子串行）到 LIS（最長遞增子串行）的經典轉化。只需要找到「(5, 2), (6, 4, 3), (5, 2), (1), ()」裡面的遞增子串行即可。

對於長度為 n 的最長遞增子串行，存在基於動態規劃的嚴格 O(n log n) 演算法，這個可以自己搜尋。

但是 A → (5, 2), (6, 4, 3), (5, 2), (1), () 這一步，序列變長了，一般來說不會退化，整個演算法還是約為 O(n log n) 的。

但是 A="aaaaa" B="aaaaaa" 這樣的資料就會退化成 O(n^2 log n)。