数据结构-KMP字符串模式匹配算法实现 （C语言代码）

解题思路:

注意事项:T S next 都是从第一个元素开始

参考代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void get_next(char T[],int next[])//next数组
{
    int i,j;
    i=0;//前
    j=1;//后
    next[1]=0;
    while(j<T[0]) {
        if(i==0 || T[i]==T[j])
        {
            i++;
            j++;
            next[j]=i;
            /*if(T[i]!=T[j])
            {
                next[j]=i;
            }
            else 
            {

                next[j]=next[i];
            }*/
        }
        else 
        {
            i=next[i];
        }
    }
}
int Index_KMP(char S[],char T[])
{
    int next[1000];
    int i=1;
    int j=1;
    get_next(T,next);//获得next数组
    /*
    for(i=1;i<=T[0];i++)
    {
            printf("%d ",next[i]);
    }
    */
    while(i<=S[0] && j<=T[0])
    {
        if(j==0||S[i]==T[j])
        {
           i++;
           j++;
        }
        else 
        {
            j=next[j];
        }
    }
    if(j>T[0])
        return i-T[0];
    return 0;

}
int main (){
    char T[1000],S[1000];
    int i,k;
    while(scanf("%s %s",S,T)!=EOF)
    {
        k=strlen(T);
        for(i=strlen(T);i>0;i--)//向后移动
        {
            T[i]=T[i-1];    
        }
        T[0]=k;
        k=strlen(S);
        for(i=strlen(S);i>0;i--)//向后移动
        {
            S[i]=S[i-1];    
        }
        S[0]=k;
        printf("%d\n",Index_KMP(S,T));
    }
    return 0;

}