這幾天看了《大話數(shù)據(jù)結構》第五章-串，重新了解了串這個數(shù)據(jù)結構，當然其中最重要的模式匹配算法KMP有了新的認識，或者說是終于理解了。
接下來結合我的理解和CSDN中大佬的詳解，講一講KMP吧！

樸素的模式匹配（BF算法、暴力算法）

簡介

這是最早、最簡單的模式匹配算法，就是簡單的暴力算法，思路：

• 主串S，模式串T
• 從主串S第一位開始和模式串T第一位開始匹配，成功匹配返回匹配成功的第一位，匹配失敗，主串S后移一位，模式串重新從頭開始匹配

代碼

//樸素的匹配,從pos位置開始匹配
int Index(string S, string T, int pos)
{
    int i = pos;
    int j = 0;
    while (i < S.length() && j < T.length())
    {
        if (S[i] == T[j])
        {
            //①如果當前字符匹配成功（即S[i] == T[j]），則i++，j++  
            ++i;
            ++j;
        }
        else
        {
            //②如果失配（即S[i]! = T[j]），令i =（i - j） + 1，j = 0  
            i = i - j + 1;
            j = 0;
        }
    } if (j == T.length())
        return i - j;
    else
        return -1;
}

例

S="goodgoogle",T="google"

1. goodgoogle
   google
2. goodgoogle
   ??google
3. goodgoogle
   ????google
4. goodgoogle
   ??????google
5. goodgoogle
   ????????google

樸素的模式匹配就是這個過程，可以看出這種算法的時間復雜度很大，為了優(yōu)化模式匹配就有了KMP算法

KMP算法

簡介

KMP是由三位前輩研究出來的避免重復遍歷的高效率模式匹配算法，它們分別是D.E.Knuth、J.H.Morris、V.R.Pratt。知道了吧KMP是來自這三位前輩的名字，我們在稱之為克努特-莫里斯-普拉特算法。

原理

通俗的講，KMP算法利用已匹配的現(xiàn)有信息，省去不必要的匹配過程，進而優(yōu)化算法。

先上一個例子解釋一下
S="abcababcax",T="abcabx"

1. abcababcax
   abcabx
2. abcababcax
   ??abcabx
3. abcababcax
   ????abcabx
4. abcababcax
   ??????abcabx
5. abcababcax
   ??????abcabx
6. abcababcax
   ??????abcabx

1前5位“abcab”匹配成功，此時S的第i位"a"與T的第j位"x"匹配失敗，i=5，j=5，按照樸素的模式匹配算法，接下來要讓T串后移一位繼續(xù)與S匹配，i變?yōu)?，j變成0，就是上面的過程，其實從1獲取的匹配信息可以知道S的前三位"abc"已與T的相應位匹配成功，且"bc"并不等于"a"，所以23步不可能匹配成功，i在第一步時已經(jīng)等于5了，但經(jīng)過2345過程5->1->2->3->4->5最后S的第i位"a"與T的第j位"c"匹配失敗,i=5，j=2?？梢园l(fā)現(xiàn)之前的2345可以去掉，i在這變化中又回到5，這個過程變化的好像只是j的值，KMP要做的就是省去不必要的匹配過程，直接跳到合適的位置。

代碼

//KMP
int KmpSearch(string S, string T, int pos)
{
    int i = pos;
    int j = 0;
    int Sl = S.length();
    int Tl = T.length();
    while (i < Sl && j < Tl)
    {
        //①如果j = -1，或者當前字符匹配成功（即S[i] == T[j]），都令i++，j++    
        if (j == -1 || S[i] == T[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1，且當前字符匹配失敗（即S[i] != T[j]），則令 i 不變，j = next[j]    
            //next[j]即為j所對應的next值      
            j = next[j];
        }
    }
    if (j == Tl)
        return i - j;
    else
        return -1;
}

next數(shù)組

前面提到合適的位置，什么叫做合適的位置呢，就是主串S與模式串T失配時，i不變，只移動模式串T到合適的位置再與S匹配，這個合適的位置就存在next數(shù)組中。
上例中第一次在i=5，j=5失配，省去不必要的過程后i=5，j=2，也就是i不變，j從5變成2，這個過程中省去的是T前兩位"ab"與S的45位"ab"匹配的過程，省去的原因是在第一次已經(jīng)匹配過了，S的"abcab"與T的"abcab"匹配，可以發(fā)現(xiàn)，T的前綴和后綴都有"ab"，則下次匹配可以從T的第2位"c"開始與S上次失配的第5位開始重新匹配。

最大相同前后綴

要計算next數(shù)組一定要知道最大相同前后綴，從上面的解釋可以知道，j的變化與模式串T有關，在失配時j=next[j]，所以要知道T最大前后綴與next數(shù)組的關系。

對于模式串T="abcabx"

串為"a"，"ab"，"abc"，時最大相同前后綴為0，"abca"為1及前后的"a"，"abcab"為2及前后的"ab"。把next 數(shù)組跟求得的最大相同前后綴對比后，不難發(fā)現(xiàn)，next 數(shù)組相當于“最大相同前后綴” 整體向右移動一位，然后初始值賦為-1。

代碼

//next數(shù)組
void GetNext(string T, int next[])
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j <T.length() - 1)
    {
        //T[k]表示前綴，T[j]表示后綴
        if (k == -1 || T[j] == T[k])
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

代碼有點難理解，我簡單解釋一下，這里涉及了已知next[0,...,j],求next[j+1]的問題。

對于T的前j+1個序列字符：

• 若T[k] == T[j]，則next[j + 1 ] = next [j] + 1 = k + 1；
• 若T[k ] ≠ T[j]，如果此時T[ next[k] ] == T[j ]，則next[ j + 1 ] = next[k] + 1，否則繼續(xù)遞歸前綴索引k = next[k]，而后重復此過程。 相當于在字符T[j+1]之前不存在長度為k+1的前綴"T0 T1, …, Tk-1 Tk"跟后綴“Tj-k Tj-k+1, …, Tj-1 Tj"相等，那么是否可能存在另一個值t+1 < k+1，使得長度更小的前綴 “T0 T1, …, Tt-1 Tt” 等于長度更小的后綴 “Tj-t Tj-t+1, …, Tj-1 Tj” 呢？如果存在，那么這個t+1 便是next[ j+1]的值，此相當于利用已經(jīng)求得的next 數(shù)組（next [0, ..., k, ..., j]）進行T串前綴跟T串后綴的匹配。
• 原文鏈接：https://blog.csdn.net/v_JULY_v/article/details/7041827

next數(shù)組的優(yōu)化

問題的出現(xiàn)

后來有人發(fā)現(xiàn)，KMP算法還是有缺陷的。
如果用之前的next 數(shù)組方法求模式串“abab”的next 數(shù)組，可得其next 數(shù)組為-1 0 0 1（0 0 1 2整體右移一位，初值賦為-1），當它跟下圖中的文本串去匹配的時候，發(fā)現(xiàn)b跟c失配，于是模式串j = next[j] =1。

abacabababc
abab

右移2位后，b又跟c失配。事實上，因為在上一步的匹配中，已經(jīng)得知p[3] = b，與s[3] = c失配，而右移兩位之后，讓p[ next[3] ] = p[1] = b 再跟s[3]匹配時，必然失配。

abacabababc
????abab

問題出在不該出現(xiàn)T[j] = T[ next[j] ]。為什么呢？理由是：當T[j] != S[i] 時，下次匹配必然是T[ next [j]] 跟S[i]匹配，如果T[j] = T[ next[j] ]，必然導致后一步匹配失?。ㄒ驗門[j]已經(jīng)跟S[i]失配，然后你還用跟T[j]等同的值T[next[j]]去跟S[i]匹配，很顯然，必然失配），所以不能允許T[j] = T[ next[j ]]。如果出現(xiàn)了T[j] = T[ next[j] ]咋辦呢？如果出現(xiàn)了，則需要再次遞歸，即令next[j] = next[ next[j] ]。
原文鏈接：https://blog.csdn.net/v_JULY_v/article/details/7041827

代碼

//優(yōu)化過后的next 數(shù)組求法
void GetNextval(string T, int next[])
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < T.length()- 1)
    {
        //T[k]表示前綴，T[j]表示后綴  
        if (k == -1 || T[j] == T[k])
        {
            ++j;
            ++k;
            //較之前next數(shù)組求法，改動在下面4行
            if (T[j] != T[k])
                next[j] = k;   //之前只有這一行
            else
                //因為不能出現(xiàn)T[j] = T[ next[j ]]，所以當出現(xiàn)時需要繼續(xù)遞歸，k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}

KMP算法時間復雜度分析

樸素的模式匹配算法時間復雜度分析如下：（n為主串長度 ，m為模式串長度）

總結

數(shù)據(jù)結構是非常重要的，這次的KMP算法也是花了好久才理解的。
歡迎批評指正。