KMP算法

原链接：http://www.nowcoder.com/live/2/5/1，本文内容由牛客网左老师的讲课内容整理而来。

KMP算法用于字符串匹配，其时间复杂度为o(n+ m)，其中n为原字符串的长度，m为匹配字符串的长度，一般n > m，所以其时间复杂度也可以认为是o(n) 

如假设有字符串str，其长度为n，匹配串是match，其长度是m，求match在str中第一次出现的位置。

KMP算法中最重要的是跳转数组next[m]，其表明了匹配串的特征，大小和match相同，其中其next[i]表示match中从下标0到i - 1的字符串的最长前缀和后缀相等的长度大小，注意，前缀不能包括下标为i-1的字条，后缀不能包括下标为0的字符，如

next数组中规定next[0] = -1(因为其没有前缀和后缀)，next[1] = 0(因其前缀是下标为i-1的字符，后缀又是下标为0的字符，违反了next定义，所以其为0)。

对于图中match= {1,2,3,1,2,3,a,a}来说，next[5]就是其下标0-4之间的字符串的特征，即其前缀与后缀相等的最长字符串为12，字符串长度为2，所以next[5] = 2;

对于图中match= {a,b,a,b,a,b,a}来说，next[6]就是match数组中其之间的字符串的特征，即其前缀和后缀最长的字符串为abab，如图中标记的所示，字符串的长度为4，所以next[6] = 4，其它值以此类推。

next数组的求法：

对于next[i] ，假设其next[i-1]已经求出，即第i-1位置上的最长前缀和后缀长度已知，假设为next[i-1] = j，如图中红色圈圈所示，a为其前缀的下一个字符，也即是match[j] = a,如果match[i-1] == a，则可以得出：next[i] = next[i - 1] +１，如果match[i - 1] != a，则比较match[i - 1]与a所在位置的前缀（第一个墨绿色圈圈）的后一个字符b（match[next[j]] = b）是否相等，如果相等，则next[i] = next[j] + 1,不相等，继续此过程，...，当next[j] == 0了，则next[i]只能是0；

代码见最后

匹配过程：

如红色箭头所示：当匹配到str中下标j位置，match中下标为5的位置时失配了，这时，next[5] = 2，则从match[2]与str[j]进行比较，依次进行下去即可，....

代码如下： (vs2010调试通过) 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *GetNext(char match[])
{
    char *next;
    int cn,pos;
    next = (char *)malloc(sizeof(char) * strlen(match));

    next[0] = -1;
    next[1] = 0;
    
    //cn表示前一个位置的next值
    //即是，如当前需要求next[i]，则cn = next[i - 1]
    cn = 0;  
    pos = 2;
    while(pos < strlen(match)){
        if(match[pos - 1] == match[cn])
            next[pos++] = ++cn;
        else if(cn > 0)
            cn = next[cn];
        else
            next[pos++] = 0;
    }
    return next;
}
//进行字符串匹配
int GetIndexOf(char str[],char match[])
{
    int sl,ml,is,im;
    char *next;
    sl = strlen(str);
    ml = strlen(match);
    next = GetNext(match);
    im = is = 0;  //is、im分别表示原字符串、匹配字符窜中的下标
    while(is < sl && im < ml){
        if(str[is] == match[im]){  
            is++;
            im++;
        }
        else if(next[im] == -1) 
            is++;
        else 
            im = next[im];
    }

    return (im == ml) ? is - im : -1;
}
int main()
{
    int res;
    char str[1024];
    char match[512];

    gets(str);
    gets(match);
    res = GetIndexOf(str,match);
    if(res >= 0)
        printf("成功匹配，其位置：%d
",res);
    else
        printf("匹配失败
");

    system("pause");
    return 0;        
}