O（n）在Boyer-Moore字符串匹配算法中構造後綴表的算法

Question

我想實現boyer-moore算法，但是我堅持構建一個我認爲應該具有O（n）複雜度的好後綴表，只發現了O（n^2）算法。 那麼你們對我有什麼線索？

請不要給我代碼片段，我可以谷歌它，如果我想，但我更喜歡用我的方式解決它，我只需要一個線索。

Answer 1

有一個使用前綴函數的快速算法。 字符串s的前綴函數是一個數組p，其中p [i]是子串s [0..i]（0-索引）及其後綴的前綴的最長長度。 它可以與利用使用2個事實KMP O（n）的複雜性計算：

1. P [I + 1] < = P [I] 1。
2. 對於每個i，如果s [p [i]] == s [i + 1]，那麼p [i + 1] = p [i] +1。否則，我們應該嘗試另一個字符串， [0 ... J-1] == S [I-J + 1 ... i]中。顯然，（我們選擇最長的字符串），我們應該跳到i = p [i-1]的位置。

該算法（C++）：

現在，我們可以構建後綴表：

m = text.length(); 
vector<int> suffshift(m); 
vector<int> pi = prefix(pattern); 
vector<int> pi1 = prefix(inverse(pattern)); 
for (int j=0; j<m; ++j) 
{ 
    suffshift[j] = m - pi[m]; 
} 
for (int i=1; i<m; ++i) 
{ 
    j = m - pi1[i]; 
    suffshift[j]=min(suffshift[j], i-pi1[i]); 
} 

Suffshift [M]代表空後綴，suppshift [0] - 爲整個文本。複雜度是O（n）。