最長公共子串

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

提示：此條目頁的主題不是最長公共子序列。

樣例

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

  ABABC
    |||
   BABCA
    |||
    ABCBA

問題定義

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

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

求解演算法

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

利用廣義字尾樹

Generalized suffix tree for the strings "ABAB", "BABA" and "ABBA", numbered 0, 1 and 2.

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

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

參考資料

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.