The Knuth-Morris-Pratt Algorithm

最簡易的子字串搜尋法，是對於每一個字元開頭 Si，判斷字串 S(i)S(i + 1)...S(i + n - 1)，是否與欲搜尋之字串 P(0)P(1)...P(n - 1)相同，然而，這樣的搜尋法複雜度為 O (n * m)，當資料量極大時，將秏費相當多的時間。

因此，為加快子字串搜尋的速度，不斷改良後，出現了名為 Knuth-Morris-Pratt 的演算法。

此演算法的精隨在於，比對失敗時，能跳過不需再比對的部分，迅速找出下一次的比對點。這與 DP 的要旨相符，「做過的就不要再做」。

Knuth 演算法如下：

對於每次的比對，若比對成功，則原字串及子字串的 index 各加 1，繼續比對。

若比對失敗，則視情況決定位移：
(1)若子字串的 index 為 0，代表開頭便不符，因此只需把原字串的 index 加 1 繼續比對。
(2)若在其他位置比對失敗，則根據位移表決定子字串的 index 移至何處繼續比對。


位移概念如下：

當原字串在位置 i 和子字串在位置 j 比對失敗，代表 P(0) ~ P(j - 1) 與 S(i - j) ~ S(i - 1) 的比對皆成功。

若字串 P(j - n)...P(j - 1) 與 P(0)...P(n - 1) 相同 （n為可行值之最大值），再根據上述條件，可知字串 P(j - n)...P(j - 1) 與 S(i - n)...S(i - 1)相同，因此可知 P(0) ~ P(n - 1) 與 S(i - n) ~ S(i - 1) 的比對皆會成功。

既然如此，只需從 P(n) 與 S(i) 比對起便可（因為確保 P(0) ~ P(n - 1) 的比對一定成功）


至於如何建表，在此就不多做說明。

快速建表法之 Code 如下：

int LengthP = Length ();   // LengthP 為子字串之長度
f[0] = -1;     // f 為表
for (int j = 1 ; j < LengthP ; ++j) {
    int i = f[j - 1];
    // str 為子字串名稱
    while ((*(str + j) != *(str + i + 1)) && (i >= 0))  
        i = f[i];
    if (*(str + j) == *(str + i + 1))
        f[j] = i + 1;
    else 
        f[j] = -1;
}