算法找到最長後綴的字符串和所述字符串的前綴之間的長度

Question

輸入：

還有很長的字符串S，我們有整數A的陣列，其表示字符串S的前綴像A[i]表示前綴S[0..A[i]]

輸出：

返回爲0相同的大小的數組其中Output[i]是S[0..A[i]]最長匹配後綴的長度和S

樣品輸入：

S = "ababa" 
A[]=[0, 1, 2, 3, 4] 

樣本輸出：

Output[]=[1,0,3,0,5]

最幼稚算法我有每個A[i]只匹配兩個字符串末尾的S[0..A[i]]和S之間的字符數。但這種算法是O(n^2)其中n是原始字符串的長度S.

問：
是否有更好的算法預先處理帶S，然後可以快速返回長度最長後綴爲整個輸入數組？

Answer 1

這僅僅是顛倒字符串的Z-function。略有不同的是，Z函數的第一個元素被選擇爲等於S的長度。有一種算法來計算在爲O（n）

而且算法針對此問題是如下字符串的Z-功能：

• S」：=反S
• ž ：= Z-函數爲每個我的S」
• ，輸出[I]：= Z [LEN（S） - A [1] - 1]

例如：

S = "baabaaa" 
A[] = [0,1,2,3,4,5,6] 
Output[] should be [0,1,2,0,1,2,7] 

S' = "aaabaab" 
Z = Z-function(S') = [7,2,1,0,2,1,0] (with the first element chosen to be Len(S)) 

Answer 2

你正在尋找被稱爲後綴樹算法/數據結構它的O(n log n)

在計算機科學中最糟糕的情況複雜，後綴樹（也稱爲PAT樹，或者在 更早表格，位置樹）是一個壓縮樹，其中包含給定文本的所有 後綴作爲它們的鍵和文本在 它們的值的位置。後綴樹允許特別快速的實現許多重要的字符串操作。 （wiki）

Here你可以找到一些幻燈片，其解釋的功能和實行詳細