2. 暴力匹配算法

假設現(xiàn)在我們面臨這樣一個問題：有一個文本串 S，和一個模式串 P，現(xiàn)在要查找 P 在 S 中的位置，怎么查找呢？

如果用暴力匹配的思路，并假設現(xiàn)在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置，則有：

• 如果當前字符匹配成功（即 S[i] == P[j]），則 i++，j++，繼續(xù)匹配下一個字符；
• 如果失配（即 S[i]! = P[j]），令 i = i - (j - 1)，j = 0。相當于每次匹配失敗時，i 回溯，j 被置為0。

理清楚了暴力匹配算法的流程及內在的邏輯，咱們可以寫出暴力匹配的代碼，如下：

int ViolentMatch(char* s, char* p)  
{  
    int sLen = strlen(s);  
    int pLen = strlen(p);  

    int i = 0;  
    int j = 0;  
    while (i < sLen && j < pLen)  
    {  
        if (s[i] == p[j])  
        {  
            //①如果當前字符匹配成功（即S[i] == P[j]），則i++，j++      
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0      
            i = i - j + 1;  
            j = 0;  
        }  
    }  
    //匹配成功，返回模式串p在文本串s中的位置，否則返回-1  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}  

舉個例子，如果給定文本串 S“BBC ABCDAB ABCDABCDABDE”，和模式串 P“ABCDABD”，現(xiàn)在要拿模式串 P 去跟文本串 S 匹配，整個過程如下所示：

1.S[0] 為 B，P[0] 為 A，不匹配，執(zhí)行第 ② 條指令：“如果失配（即 S[i]! = P[j]），令 i = i - (j - 1)，j = 0”，S[1] 跟 P[0] 匹配，相當于模式串要往右移動一位（i=1，j=0）

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/1.png" alt="" />

2.S[1] 跟 P[0] 還是不匹配，繼續(xù)執(zhí)行第 ② 條指令：“如果失配（即 S[i]! = P[j]），令 i = i - (j - 1)，j = 0”，S[2] 跟 P[0] 匹配（i=2，j=0），從而模式串不斷的向右移動一位（不斷的執(zhí)行“令 i = i - (j - 1)，j = 0”，i 從 2 變到 4，j 一直為 0）

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/2.png" alt="" />

3.直到 S[4] 跟 P[0] 匹配成功（i=4，j=0），此時按照上面的暴力匹配算法的思路，轉而執(zhí)行第 ① 條指令：“如果當前字符匹配成功（即 S[i] == P[j]），則 i++，j++”，可得 S[i] 為 S[5]，P[j] 為 P[1]，即接下來 S[5] 跟 P[1] 匹配（i=5，j=1）

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/3.png" alt="" />

4.S[5] 跟 P[1] 匹配成功，繼續(xù)執(zhí)行第 ① 條指令：“如果當前字符匹配成功（即 S[i] == P[j]），則 i++，j++”，得到 S[6] 跟 P[2] 匹配（i=6，j=2），如此進行下去

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/4.png" alt="" />

5.直到 S[10] 為空格字符，P[6] 為字符 D（i=10，j=6），因為不匹配，重新執(zhí)行第 ② 條指令：“如果失配（即 S[i]! = P[j]），令 i = i - (j - 1)，j = 0”，相當于 S[5] 跟 P[0] 匹配（i=5，j=0）

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/5.png" alt="" />

6.至此，我們可以看到，如果按照暴力匹配算法的思路，盡管之前文本串和模式串已經分別匹配到了 S[9]、P[5]，但因為 S[10] 跟 P[6] 不匹配，所以文本串回溯到 S[5]，模式串回溯到 P[0]，從而讓 S[5] 跟 P[0] 匹配。

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/6.png" alt="" />

而 S[5] 肯定跟 P[0] 失配。為什么呢？因為在之前第 4 步匹配中，我們已經得知 S[5] = P[1] = B，而 P[0] = A，即 P[1] != P[0]，故 S[5] 必定不等于 P[0]，所以回溯過去必然會導致失配。那有沒有一種算法，讓 i 不往回退，只需要移動 j 即可呢？

答案是肯定的。這種算法就是本文的主旨 KMP 算法，它利用之前已經部分匹配這個有效信息，保持 i 不回溯，通過修改 j 的位置，讓模式串盡量地移動到有效的位置。