KMP算法C实现

 这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的，因此人们称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。

     其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);

char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;

int main()
{
    int n;
    get_next(t,next);
    n=index_KMP(s,t,pos);
    printf("%d",n);
    return 0;
}

int index_KMP(char *s,char *t,int pos)
{
    int i=pos,j=1;
    while (i<=(int)strlen(s)&&j<=(int)strlen(t))
    {
        if (j==0||s[i]==t[j-1])
        {
            i++;
            j++;
        }
        else j=next[j];
    }
    if (j>(int)strlen(t))
        return i-strlen(t)+1;
    else 
        return 0;
}

void get_next(char *t,int *next)
{

    int i=1,j=0;
    next[0]=next[1]=0;
    while (i<(int)strlen(t))
    {
        if (j==0||t[i]==t[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else j=next[j];
    }

}