算法-KMP模式匹配算法学习

KMP的时间复杂度是O(M+N);

KMP的关键是求Next数组。

Next数组的意思是，当每次匹配失败的时候，保持i不变，j定位到next(j)这个位置，重新开始匹配。

Next数组的由来:

第一行是S字符串，第二行是P字符串

例1：next[]

0 1 2 3 4 5 6 7 8 9 i=6

ZWA BA BAB EGHIJK

A BA BE

0 1 2 3 4 j=4

0 1 2 3 4 5 6 7 8 9 i=6 (不变)

ZWA BA BA B E G HIJK

A BA BE

0 1 2 3 4 j=2 (说明next(4)=2)

途中绿色块和黄色块是重叠的，当i=6,j=4的时候A!=E不匹配，不需要用传统的i=2,j=0回溯，而是将P字符串的绿色块去对应S字符串的黄色字符串，因为肉眼看出黄色和绿色是相等的，而且长度刚好为2，巧合的是重新匹配的位置j=2, 这个2正好是S字符串的j下标移动的位置，也就是说：当i=6,j=4失败的时候，j=next(j) 也就是j=next(4)=2; 那为啥刚好是2呢，下面看例2.

例2：

0 1 2 3 4 5 6 7 8 9 i=8

ZWA BCA BCA B EGHIJK

A BCA BC E

01 2 3 4 5 6 j=6

0 1 2 3 4 56 7 8 9 i=8(不变)

ZWA B CA BCA BEGHIJK

A B C A BCE

0 1 2 3 45 6 j=3(说明next(6)=3)

当绿色和黄色块重叠部分变成3的时候，相应的: 当i=8,j=6不匹配的时候， j=next(j)=next(6)=3; 这不是巧合。

总结出之前提出的一个理论。那就是next(j) 的值刚好等于 [0, j-1] 闭区间，他们首部和尾部重合的长度。经前人证明这个是区间内首部和尾部重合最大的长度。

比如 ababab 这个是2

abcda 这个是1

下面是求next数组的算法:

按照递推的思想：

根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]

1)若P[j]==P[k]，则有P[0..k]==P[j-k+1,j]，很显然，next[j+1]=next[j]+1=k+1;

2)若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移动，显然k=next[k]。

自从大学上数据结构课的时候，“串“那一章接触到KMP算法，不过当时咋一看，没看懂，而且老师又没有细讲，就不了了之了，后来算法分析课又讲到了这个，当时好像是弄懂了，但是2年下来，偶然看到这个算法，又蒙了。看来当时还是没把思想牢牢的把握。现在懂得了一个道理，学程序或者算法真的不能只靠记忆，这样只能当时了解一下，时过境迁就忘了，仅剩KMP有印象。有幸的是看到了一个算法大神的博文http://blog.csdn.net/v_july_v/article/details/7041827

让我对KMP有了更加深层的理解了。

KMP

next[j]就是T字符串的前缀和后缀最大的重叠长度。

主要是求next数组
void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}  

int KmpSearch(char* s, char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}