此文是嚴蔚敏的數(shù)據(jù)結構課程有關KMP算法相關課程 - KMP算法講解P12 的理解記錄。

模式串匹配原始算法

模式串匹配最原始的算法是：分別利用計數(shù)指針 i 和 j 指示主串 S 和模式串 T 中當前正待比較的字符位置缘揪。算法的基本思想是：從主串 S 的第 pos 個字符起和模式的第一個字符比較之钓株，若相等，則繼續(xù)逐個比較后續(xù)字符抵赢；否則從主串 S 的下一個字符起再重新和模式串 T 的字符比較之津肛。以此類推，直至模式串 T 中的每個字符依次和主串 S 中的一個連續(xù)的字符序列相等，則稱匹配成功聂示，函數(shù)值為和模式串 T 中第一個字符相等的字符在主串 S 中的序號，否則稱匹配不成功簇秒，函數(shù)值為零鱼喉。 其算法如下所示：
原始算法

int Index(SString S, SString T, int pos) {
    // 返回子串 T 在主串 S 中第 pos 個字符之后的位置。若不存在趋观，則函數(shù)值為0扛禽。
    // 其中，T 非空皱坛，1 <= pos <= StrLength(S)编曼。
    i = pos;    j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (S[i] == T[j]){ ++i;    ++j; }  // 繼續(xù)比較后繼字符
        else { i = i - j + 2;    j = 1; }
    }
    if (j > T[0])    return i - T[0];
    else return 0;
} // Index

這種原始算法因為其 i 指針和 j 指針在不匹配的時候都需要回溯，我們可以得到在最壞情況下其的時間復雜度為 O(n * m)剩辟。所以便有了改進算法 - KMP算法

模式串匹配改進算法 - KMP算法

這種改進算法是 D.E.Knuth 與 V.r.Pratt 和 J.H.Morris 同時發(fā)現(xiàn)的掐场，因此人們稱它為 克努特 - 莫里斯 - 普拉特操作（簡稱為KMP算法）。此算法可以在 O(n + m) 的時間數(shù)量級上完成串的模式匹配操作贩猎。其改進在于：每當一趟匹配過程中出現(xiàn)字符串比較不等時熊户，不需回溯 i 指針，而是利用已經(jīng)得到的“部分匹配”的結果將模式向右“滑動”盡可能遠的一段距離后融欧，繼續(xù)進行比較敏弃。

假設主串為 s1s2···sn ，模式串為 p1p2···pm 噪馏，為了實現(xiàn)改進算法麦到，需要解決下述問題：當匹配過程中產(chǎn)生“失配”（即si != pj ）時，模式串“向右滑動”可行的距離多遠欠肾，換句話說瓶颠，當主串第 i 個字符與模式中第 j 個字符“失配”（即比較不等）時，主串中第 i 個字符（ i 指針不回溯）應與模式中哪個字符再比較刺桃？

假設此時應與模式串 T 中第 k (k < j)個字符繼續(xù)比較粹淋，則模式串 T 中前 k - 1 個字符的子串必須滿足下列關系式，且不可能存在 k’ > k 滿足下列關系式
關系式①：p1p2···pk-1 = si-k+1 si-k+2···si-1
而已經(jīng)得到的“部分匹配”的結果是
關系式②：pj-k+1 pj-k+2···sj-1 = si-k+1si-k+2···si-1
由關系式①和關系式②推得下列等式
關系式③：p1p2···pk-1 = pj-k+1 pj-k+2···pj-1

反之瑟慈，若模式串中存在滿足關系式③的兩個子串桃移，則當匹配過程中，主串 S 中的第 i 個字符與模式串 T 中第 j 個字符比較不等時葛碧，僅需將模式串 T 向右滑動至模式串 T 第 k 個字符和主串 S 中第 i 個字符對齊借杰，此時，模式串 T 中頭 k - 1 的子串 p1p2···pk-1 必定與主串中第 i 個字符之前的長度為 k - 1 的子串 si-k+1 si-k+2···si-1 相等进泼，由此蔗衡，匹配僅需從模式串 T 中第 k 個字符與主串 S 中第 i 個字符比較起繼續(xù)進行。

若令 next[j] = k乳绕，則 next[j] 表明當模式串 T 中第 j 個字符與主串中相應字符“失配”時绞惦，在模式串 T 中需重新和主串 S 中該字符進行比較的字符的位置。由此引出模式串 T 的 next 函數(shù)的定義：

由此定義可推出下列模式串中的 next 函數(shù)值：

在求得模式串 T 的 next 函數(shù)之后洋措，匹配可如下進行：假設以指針 i 和 j 分別指示主串 S 和 模式串 T 中正待比較的字符济蝉，令 i 的初值為 pos，j 的初值為 1菠发。若在匹配過程中 si = pj 王滤，則 i 和 j 分別增 1，否則 i 不變雷酪，而 j 退到 next[j] 的位置在比較淑仆，若相等，則指針各自增 1哥力，否則 j 再退到下一個 next 值的位置蔗怠，依次類推，直至下列兩種可能：

• 一種是 j 退到某個 next 值（next[next[···next[j]···]]）時字符比較相等吩跋，則指針各自增 1寞射，繼續(xù)進行匹配；
• 另一種是 j 退到值為零（即模式的第一個字符“失配”）锌钮，則此時需將模式串 T 繼續(xù)向右滑動一個位置桥温，即從主串的下一個字符 si+1起和模式串 T 重新開始匹配。

KMP算法如下所示：它在形式上和原始算法極為相似梁丘。不同之處在于匹配過程中產(chǎn)生“失配”時侵浸，指針 i 不變旺韭，指針 j 退回到 next[j] 所指示的位置上重新進行比較，并且當指針 j 退至零時掏觉，指針 i 和指針 j 同時增 1区端。即若主串 S 的第 i 個字符和模式串 T 的第一個字符不等，應從主串的第 i + 1 個字符起重新進行匹配澳腹。

KMP算法

int Index_KMP(SString S, SString T, int pos) {
    // 利用模式串 T 的 next 函數(shù)求 T 在主串中第 pos 個字符之后的位置的KMP算法织盼。
    // 其中，T 非空酱塔，1 <= pos <= StrLength(S)沥邻。
    i = pos;    j = 1;
    while (i <= S[0] && j <= T[0]) {
        if ( j == 0 || S[i] == T[j]){ ++i;    ++j; }  // 繼續(xù)比較后繼字符
        else { j = next[j]; }
    }
    if (j > T[0])    return i - T[0];
    else return 0;
} // Index_KMP

next 函數(shù)算法

KMP算法是在已知模式串的 next 函數(shù)值的基礎上執(zhí)行的，那么羊娃，如何求得模式串的 next 函數(shù)值呢唐全？

從上述討論可見，此函數(shù)值僅取決于模式串本身而和相匹配的主串無關迁沫。我們可從分析其定義出發(fā)芦瘾，用遞推的方法求得 next 函數(shù)值。

由定義得知: next[1] = 0
設 next[j] = k集畅，這表明在模式串中存在下列關系：p1p2···pk-1 = pj-k+1 pj-k+2···pj-1
其中 k 滿足 1 < k < j 的某個值近弟，并且不可能存在 k’ > k 滿足等式 p1p2···pk-1 = pj-k+1 pj-k+2···pj-1 ，此時 next[j+1] = ? 可能有兩種情況：

1. 若 pk = pj 挺智，則表明在模式串中 p1p2···pk = pj-k+1 pj-k+2···pj 祷愉，并且不可能存在 k’ > k 滿足等式 p1p2···pk = pj-k+1 pj-k+2···pj，這就是說 next[j+1] = next[j] + 1 赦颇。
2. 若 pk != pj 二鳄，則表明在模式串中 p1p2···pk != pj-k+1 pj-k+2···pj ，此時可把求 next 函數(shù)值的問題看成是一個模式匹配的問題媒怯，整個模式串既是主串又是模式串订讼，而當前在匹配過程中，已有 pj-k+1 = p1, pj-k+2 = p2,···扇苞，pj-1 = pk-1欺殿，則當 pk != pj 時應將模式串向右滑動至以模式串中的第 next[k] 個字符和主串中的第 j 個字符向比較。若 next[k] = k’鳖敷，且 pj = pk’脖苏，則說明在主串中第 j + 1 個字符之前存在一個長度為 k’（即next[k]的最長子串，和模式串中從首字符起長度為 k’ 的子串相等）定踱，即 p1p2···pk = pj-k+1 pj-k+2···pj ( 1 < k’ < k < j)棍潘，這就是說 next[j+1] = k’ + 1，即 next[j+1] = next[k] + 1。同理若 pj != pk’亦歉，則將模式繼續(xù)向右滑動直至將模式串中的第 next[k’] 個字符和 pj 對齊恤浪，······，依次類推鳍徽，直至 pj 和模式串中的某個字符匹配成功或者不存在任何 k’(1 < k’ < j) 滿足 p1p2···pk = pj-k+1 pj-k+2···pj资锰，則 next[j + 1] = 1敢课。

next 函數(shù)算法

void get_next(SString T, int next[]) {
    // 求模式串 T 的 next 函數(shù)值并存入數(shù)組 next阶祭。
    i = 1;  next[1] = 0;  j = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;  ++j;  next[i] = j;
        }else {
            j = next[j];
        }
    }   
}// get_next