前言
據(jù)統(tǒng)計，在所有程序中刑峡，關(guān)于字符串處理的程序占到了百分之八十以上肉渴，所以關(guān)于字符串處理的算法十分多，而且關(guān)于數(shù)字處理的很多算法同樣可以用于字符串中叔遂，包括本文提到的快速排序，除此之外關(guān)于字符串還有很多其他的算法争剿，比如回文串已艰，重復(fù)子串等等，這些問題還可以組合成為更復(fù)雜的問題蚕苇，在字符串處理中哩掺，有一些較復(fù)雜或者說適用性不廣的算法，即這個算法只對這類題目適用涩笤，但是他確實很巧妙嚼吞。當(dāng)然這些都不是重點盒件，重點是將算法當(dāng)作藝術(shù)去品，看見其魅力便可舱禽。閑話少說炒刁，開始正文。
問題
這個問題有很多版本誊稚，下面的便是一種經(jīng)典的出題方式（題目來自于網(wǎng)上）：
給定一個文本文件作為輸入翔始，查找其中最長的重復(fù)子字符串。例如里伯，"Ask not what your country can do for you, but what you can do for your country"中最長的重復(fù)字符串是“can do for you”城瞎，第二長的是"your country"。
講解
看完這個題目俏脊，片刻思忖全谤，相信大多數(shù)人會和我一樣得到最naive的解法，暴力解決辦法爷贫，枚舉遍歷等等认然，因為這個題目本身給人一種重復(fù)性很強(qiáng)的感覺，所以算法的時間復(fù)雜度不會太低漫萄，想在O(N)時間內(nèi)解決基本不大可能卷员。naive的解法有我經(jīng)過思考和參考列舉下面兩種，不附代碼了腾务，只用文字描述毕骡。
- 第一種方法，時間復(fù)雜度：O(N^3)
如下圖：有一個字符串“abacdbacf”岩瘦，我們用兩個指針未巫，p1從頭開始，p2從p1+1開始启昧，進(jìn)行兩層循環(huán)叙凡，在每層循環(huán)內(nèi)部，尋找p1和p2所指的字符串的最長公共子串密末，這個思路比較簡單握爷，時間復(fù)雜度也容易求得，偽代碼如下：
def find_longest_repeating_strings(string):
for p1 in range(len(string)):
for p2 in range(p1+1, len(string)):
max = find_common_string()
return max
- 第二種方法严里，時間復(fù)雜度：O(N^3)
和第一種方法十分類似新啼，都是遍歷的思想，這次從長度開始刹碾，同樣用兩個指針燥撞，只是外層循環(huán)從1到字符串長度來控制p1和p2所指的要比較子串的長度，時間復(fù)雜度也十分容易分析，偽代碼如下：
def find_longest_repeating_strings(string):
for i in range(1, len(string)):
for p1 in range(len(string)-i):
for p2 in range(p1+1, len(string)-i):
max = find_common_string()
return max
- 第三種方法物舒，時間復(fù)雜度：O(N^2logN)
這種方法用到了后綴數(shù)組辆布，后綴數(shù)組是什么呢？用我自己理解來說茶鉴，后綴是相對于前綴來說锋玲，前綴就是一個字符串的左子集，那后綴就是字符串的右子集涵叮，字符串的所有右子集的集合便組成了后綴數(shù)組惭蹂。比如字符串“abc”的后綴數(shù)組就是["abc","bc","c"]，很好理解吧割粮。接下來先講解第三種方法盾碗，以“abacdbacf”為例，然后再講為什么這樣可以舀瓢，我想像我這種見識少的人會吃驚的廷雅。
- 求字符串的后綴數(shù)組
求解方法剛才已經(jīng)說過，得到的后綴數(shù)組為：[abacdbacf,bacdbacf,acdbacf,cdbacf,dbacf,bacf,acf,acf,cf,f] - 將字符串的后綴數(shù)組按照字典序進(jìn)行排序
可以使用任何方法將后綴數(shù)組進(jìn)行排序京髓，排序是按照字符的ASCII排序航缀，我這里選擇的是快速排序。排序后的結(jié)果為：['abacdbacf', 'acdbacf', 'acf', 'bacdbacf', 'bacf', 'cdbacf', 'cf', 'dbacf', 'f'] - 兩兩從頭比較比較排序后的后綴數(shù)組相鄰的兩個字符串的公共子串
分別比較后綴數(shù)組里面相鄰的兩個字符串的公共子串堰怨，得到的最長公共子串即為題目所求芥玉，比如“abacdbacf”和“acdbacf”的最長公共子串為“a”，注意這里只需要從頭比較备图，比如“banana”和“ana”的最長公共子串為“”灿巧，而不是“ana”，至于原因揽涮，接下來解釋抠藕。
操作的步驟講解完畢，由于在快速排序中我們的時間復(fù)雜度可以達(dá)到O(NlogN)蒋困，所以最終的時間復(fù)雜度減少了盾似，為O(N^2logN)，為什么可以這樣做呢家破？考慮第一種用兩個指針的方法颜说，不失一般性购岗，假設(shè)現(xiàn)在指針指向了任意兩個字符x,y,接下來需要的便是比較其指向的字符串的公共子串汰聋，這和先求后綴子串其實是一個道理，那求后綴子串的優(yōu)勢在哪里呢喊积？不用挨個重復(fù)遍歷烹困，在得到了后綴數(shù)組之后，我們按照字典序進(jìn)行排序乾吻，所有具有最長公共子串的肯定會相鄰髓梅，所以在得到排好序的后綴數(shù)組之后拟蜻，只需要O(N)的時間復(fù)雜度便可得到結(jié)果，但是要注意這里的最長公共子串是從第一個字符串開始比較枯饿，一旦不同酝锅，立馬返回，比如“banana”和“ana”的最長公共子串為“”奢方，而不是“ana”搔扁，因為您只要稍微想一下，就會發(fā)現(xiàn)蟋字，“anana”也是后綴數(shù)組中的一元素稿蹲。最后附上代碼如下，或者直接從github下載：
def partition(suffix_array, start, end):
if end <= start:
return
index1, index2 = start, end
base = suffix_array[start]
while index1 < index2 and suffix_array[index2] >= base:
index2 -= 1
suffix_array[index1] = suffix_array[index2]
while index1 < index2 and suffix_array[index1] <= base:
index1 += 1
suffix_array[index2] = suffix_array[index1]
suffix_array[index1] = base
partition(suffix_array, start, index1 - 1)
partition(suffix_array, index1 + 1, end)
def find_common_string(str1, str2):
if not str1 or not str2:
return 0, ''
index1, index2 = 0, 0
length, comm_substr = 0, ''
while index1 < len(str1) and index2 < len(str2):
if str1[index1] == str2[index2]:
length += 1
comm_substr += str1[index1]
else:
break
index1 += 1
index2 += 1
return length, comm_substr
def find_longest_repeating_strings(string):
if not string:
return None, None
suffix_array = []
# first, get the suffix arrays
length = len(string)
for i in range(length):
suffix_array.append(string[i:])
# second, sort suffix array
start, end = 0, len(suffix_array) - 1
partition(suffix_array, start, end)
# third, get the longest repeating substring
max_length, repeat_substring = 0, ''
for i in range(len(suffix_array) - 1):
common_len, common_substring = find_common_string(suffix_array[i], suffix_array[i+1])
if common_len > max_length:
max_length, repeat_substring = common_len, common_substring
return max_length, repeat_substring
if __name__ == "__main__":
string = "Ask not what your country can do for you, but what you can do for your country"
length, substr = find_longest_repeating_strings(string)
print length, substr
總結(jié)
關(guān)于字符串的處理有太多的巧招妙招鹊奖，本文只是其中的一種苛聘，總之自己看完這種解法之后，大呼美妙~
不向靜中參妙理,縱然穎悟也虛浮 立乎其大 和而不同 古之成大事者忠聚，不惟有超世之才设哗，亦必有堅韌不拔之志
