字符串操作：計算「字符串與其後綴的相似性」

Question

對於兩個字符串A和B，我們將字符串的相似性定義爲兩個字符串共有的最長前綴的長度。例如，字符串「abc」和「abd」的相似性爲2，而字符串「aaa」和「aaab」的相似性爲3.

問題是給出一種算法來計算相似度總和一個帶有每個後綴的字符串S.例如，讓字符串爲：ababaa。然後，字符串的後綴是ababaa,babaa, abaa,baa,aa和a。這些字符串與字符串ababaa的相似性分別爲6,0,3,0,1,1。因此答案是6 + 0 + 3 + 0 + 1 + 1 = 11。

Answer 1

你想考慮suffix arrays。單詞的後綴數組是按字典順序排序的後綴索引數組。在鏈接的維基百科文章中，算法在計算後綴數組時計算LCP（最長公共前綴）。您可以使用與suffix trees的相似性在O(n)中計算此值，如this paper中所示。

實施例：您的字符串爲ababaa，所以後綴數組看起來像這樣：

5 | a 
4 | aa 
2 | abaa 
0 | ababaa 
3 | baa 
1 | babaa 

其中左邊的數字是後綴開始處的索引。現在每個計算前綴都很棒，因爲一切都按照字典順序存儲。

請注意，這與longest common substring問題密切相關。爲了練習下次面試，請考慮如何有效解決這個問題。