KMP算法

首先，要了解两个概念:'前缀'和'后缀'.＂前缀＂指除了最后一个字符以外,一个字符串的全部头部组合；＂后缀＂指除了第一个字符以外，一个字符的全部尾部组合.而在这里next[j]的值就是＂前缀＂和后缀的最长的共有元素的长度，在这里以"ABAABCAC"

next[0]:j=0,"A"的前缀和后缀都为空集,共有的元素的长度为０;

next[1]:j=1"AB"的前缀为[A]，后缀为[B]，共有元素的长度0.

next[2]:j=2"ABA"的前缀为[A,AB]，后缀为[BA,A],共有元素为"A",长度为1.

next[3]:j=3"ABAA"的前缀为[A,AB,ABA],后缀为[BAA,AA,A],共有元素为"A"长度为1.

next[4]:j=4"ABAAB"的前缀为[A,AB,ABA,ABAA]，后缀为[BAAB,AAB,AB,B]，共有元素为'AB'，长度为2;

next[5]:j=5"ABAABC"的前缀为[A,AB,ABA,ABAA,ABAAB],后缀为[BAABC,AABC,ABC,BC,C]，共有元素的长度为０;

next[6]:j=6"ABAABCA"的前缀为[A,AB,ABA,ABAA,ABAAB,ABAABC]，后缀为[BAABCA,AABCA,ABCA,BCA,CA,A]，共有元素为＂A＂长度为1;

next[7]:j=7"ABAABCAC"的前缀为[A,AB,ABA,ABAA,ABAAB,ABAABC,ABAABCA],后缀为[BAABCAC,AABCAC,ABCAC,BCAC,CAC,AC,C]共有元素的长度为０．

用一个具体的例子来主串ACABAABAABCACAABC;

模式串:ABAABCA;

具体代码如下:

#include<stdio.h>
#include <string.h>
void Mnext(char mod[],int next[])
{
    int len=strlen(mod);
    int i=1,k=0;
    next[0]=0;
    while(i<len)
    {
        while(k>0 && mod[k]!=mod[i])
        {
            k=next[k-1];//返回到上一层的匹配点继续匹配，如果不匹配，继续返回，直到k＝０,说明都不匹配;此时的next值为0;
        }
        if(mod[k]==mod[i])
        {
            k++;
        }
        next[i]=k;
        i++;
    }
}
int kmp(char s[],char m[])
{
    int L1=strlen(s);
    int L2=strlen(m);
    int next[L2];
    int i=0,j=0;
    Mnext(m,next);
    while(i<L1)
    {
        while(j > 0 && s[i] != m[j])
        {
            j=next[j-1];
        }
        if(s[i] == m[j])
        {
           j++;
        }
        if(j==L2)
        {
            return i-j+1;
        }
        i++;
    }
}
int main()
{
    int n;
    char s[]="ACABAABAABCACAABC";
    char m[]="ABAABCA";
    n=kmp(s,m);
    printf("模式串%s在主串%s中的下标为:%d\n",m,s,n);
    return 0;

}