最長公共子串

在計算機科學中，最長公共子串問題是尋找兩個或多個已知字符串最長的子串。此問題與最長公共子序列問題的區別在於子序列不必是連續的，而子串卻必須是。

樣例

字符串"ABABC"，"BABCA"以及"ABCBA"的最長公共子串是"ABC"。其他的公共子串包括"A"、"AB"、"B"、"BA"、"BC"以及"C"。

  ABABC
    |||
   BABCA
    |||
    ABCBA

問題定義

給定兩個字符串，長度為 $m$ 的字符串 $S$ 以及長度為 $n$ 的字符串 $T$ ，求最長的子串 $x$ 同時是 $S$ 以及 $T$ 的連續子串。

問題可以一般化為k-公共子串問題——給定字符串的集合 ${\displaystyle S=\{S_{1},...,S_{K}\}}$ ，其中 $|S_{i}|=n_{i}$ ， $\Sigma n_{i}=N$ .。對於滿足 $2\leq k\leq K$ 的 $k$ ，找出至少是 $S$ 中 $k$ 個字符串的公共子串的最長串。

求解算法

利用廣義後綴樹，我們可以在 $\Theta (n+m)$ 的時間複雜度內求出 $S$ 和 $T$ 的最長公共子串的長度和他們的起始位置。而如果利用動態規劃求解，則時間複雜度為 $\Theta (nm)$ 。而對於一般化的公共子串問題，使用動態規劃的求解的時間複雜度為 $\Theta (n_{1}$ ·...· $n_{K})$ ，利用廣義後綴樹則需 $\Theta (N*K)$ 的時間複雜度。

利用廣義後綴樹

字符串集合的最長公共子串可以通過構造一棵廣義後綴樹, 然後去查找擁有來自所有集合中字符串的葉節點的最深的內部節點來得到。右圖展示了字符串「ABAB」，「BABA」和「ABBA」對應的廣義後綴樹。為了方便後綴樹的構造和區分字符串，每個串的結尾都添加了終結符「$」和字符串編號，分別變成了「ABAB$0」，「BABA$1」和「ABBA$2」。如圖所示，串「A」，「B」,「AB」和「BA」的節點對應的子樹都包含來自所有字符串的葉節點。

假定字母表的大小是常數，構造這樣的一顆後綴樹的時間複雜度為 $\Theta (N)$ 。這樣，如果將整個樹自底向上遍歷，並在每個節點通過一個位向量標記每個節點的子樹中出現過的所有字符串的，則k-公共子串問題可以以 $\Theta (NK)$ 的時間複雜度來解決。特別地，如果後綴樹為常數時間的最近公共祖先檢索做了優化，那麼問題將可以在 $\Theta (N)$ 的時間複雜度內解決.^[1]

參考資料

^ Gusfield, Dan. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. 1999 [1997]. ISBN 0-521-58519-8.

[Gus97-1] Gusfield, Dan. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. 1999 [1997]. ISBN 0-521-58519-8.

[1]