-
最長公共子串
鎖定
- 中文名
- 最長公共子串
- 外文名
- Longest common substring
- 本 質
- 尋找兩個或多個字符串最長的子串
最長公共子串樣例
字符串"ABABC","BABCA"以及"ABCBA"的最長公共子串是"ABC"。其他的公共子串包括"A"、"AB"、"B"、"BA"、"BC"以及"C"。
ABABC
|||
BABCA
|||
ABCBA
最長公共子串問題定義
給定兩個字符串,長度為
的字符串
以及長度為
的字符串
,求最長的子串
同時是
以及
的連續子串。
問題可以一般化為k-公共子串問題——給定字符串的集合
,其中
,
。對於滿足
的
,找出至少是
中
個字符串的公共子串的最長串。
最長公共子串求解算法
利用廣義後綴樹,我們可以在
的時間複雜度內求出
和
的最長公共子串的長度和他們的起始位置。而如果利用動態規劃求解,則時間複雜度為
。而對於一般化的公共子串問題,使用動態規劃的求解的時間複雜度為
·...·
,利用廣義後綴樹則需
的時間複雜度。
利用廣義後綴樹
字符串集合的最長公共子串可以通過構造一棵廣義後綴樹, 然後去查找擁有來自所有集合中字符串的葉節點的最深的內部節點來得到。圖1展示了字符串“ABAB”,“BABA”和“ABBA”對應的廣義後綴樹。為了方便後綴樹的構造和區分字符串,每個串的結尾都添加了終結符“$”和字符串編號,分別變成了“ABAB$0”,“BABA$1”和 “ABBA$2”。如圖1所示,串“A”,“B”,“AB”和“BA”的節點對應的子樹都包含來自所有字符串的葉節點。