[科普中國(guó)]-最長(zhǎng)公共子串行

在計(jì)算機(jī)科學(xué)中，最長(zhǎng)公共子串問(wèn)題是尋找兩個(gè)或多個(gè)已知字符串最長(zhǎng)的子串。此問(wèn)題與最長(zhǎng)公共子序列問(wèn)題的區(qū)別在于子序列不必是連續(xù)的，而子串卻必須是。

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

ABABC

|||

BABCA

|||

ABCBA

問(wèn)題定義給定兩個(gè)字符串，長(zhǎng)度為的字符串以及長(zhǎng)度為的字符串，求最長(zhǎng)的子串同時(shí)是以及的連續(xù)子串。

問(wèn)題可以一般化為k-公共子串問(wèn)題——給定字符串的集合，其中，。對(duì)于滿足的，找出至少是中個(gè)字符串的公共子串的最長(zhǎng)串。

求解算法利用廣義后綴樹(shù)，我們可以在的時(shí)間復(fù)雜度內(nèi)求出和的最長(zhǎng)公共子串的長(zhǎng)度和他們的起始位置。而如果利用動(dòng)態(tài)規(guī)劃求解，則時(shí)間復(fù)雜度為。而對(duì)于一般化的公共子串問(wèn)題，使用動(dòng)態(tài)規(guī)劃的求解的時(shí)間復(fù)雜度為·...·，利用廣義后綴樹(shù)則需的時(shí)間復(fù)雜度。

利用廣義后綴樹(shù)

字符串集合的最長(zhǎng)公共子串可以通過(guò)構(gòu)造一棵廣義后綴樹(shù), 然后去查找擁有來(lái)自所有集合中字符串的葉節(jié)點(diǎn)的最深的內(nèi)部節(jié)點(diǎn)來(lái)得到。圖一展示了字符串“ABAB”，“BABA”和“ABBA”對(duì)應(yīng)的廣義后綴樹(shù)。為了方便后綴樹(shù)的構(gòu)造和區(qū)分字符串，每個(gè)串的結(jié)尾都添加了終結(jié)符“$”和字符串編號(hào)，分別變成了“ABAB$0”，“BABA$1”和 “ABBA$2”。如圖所示，串“A”，“B”,“AB”和“BA”的節(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)都包含來(lái)自所有字符串的葉節(jié)點(diǎn)。

假定字母表的大小是常數(shù)，構(gòu)造這樣的一顆后綴樹(shù)的時(shí)間復(fù)雜度為。這樣，如果將整個(gè)樹(shù)自頂向上遍歷，并在每個(gè)節(jié)點(diǎn)通過(guò)一個(gè)位向量標(biāo)記每個(gè)節(jié)點(diǎn)的子樹(shù)中出現(xiàn)過(guò)的所有字符串的，則k-公共子串問(wèn)題可以以的時(shí)間復(fù)雜度來(lái)解決。特別地，如果后綴樹(shù)為常數(shù)時(shí)間的最近公共祖先檢索做了優(yōu)化，那么問(wèn)題將可以在的時(shí)間復(fù)雜度內(nèi)解決。1

本詞條內(nèi)容貢獻(xiàn)者為:

胡啟洲 - 副教授 - 南京理工大學(xué)