kmp算法

kmp算法是模式匹配算法,用于查找模式串P在字符串S中的位置。

比如,S为“BBC ABCDAB ABCDABCDABDE”模式串P为“ABCDABD“

一种O(M*N)的方法就是用P和S的每个字符串进行匹配,称为暴力解法

算法如下(来自http://blog.csdn.net/v_july_v/article/details/7041827)

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;  
}  

kmp

上图是暴力匹配中的一个步骤,因为D和空格不匹配,所以下一步应该是这个样子
kmp

但是我们明显看出,P中有两个”AB“字串,在D和空格匹配失败后,空格前面的“AB”和P中的头两个字母“AB”应该是能匹配的,所以下一步应该是这个样子

kmp

那么怎样得出这样的结果呢?

答案是依靠一个next数组,该数组中i的位置记录了[0,i)的范围内结尾是i-1的所有字串和字串[0,i)的共同前缀的最大长度。所以在D和空格不匹配的时候,P的next数组应该是这样的

A B C D A B D

-1 0 0 0 0 1 2

所以在D没有匹配成功的情况下,S的i保持不变,P的j移动到index为2的位置继续匹配,

这个时候P的next数组应该是

-1 0 0 0

next数组的求法