用C语言实现KMP算法

用C语言实现KMP算法

#include<stdio.h>
#include<string.h>
typedef struct SString{
    char ch[100];
    int length;
}SString;
int Index_KMP(SString S,SString T,int next[]){
    //利用模式串T的next函数求T在主串S中第pos个字符之后的位置
    //其中,T非空,1<=pos<=S.length
    int i,j;
    i=0;j=1;
    while(i<=S.length&&j<=T.length)//两个字符串均未比较到串尾
    {
        if(j==0||S.ch[i]==T.ch[j]){++i;++j;}//继续比较后继字符串
        else j=next[j];//模式串向后移动
    }
    if(j>T.length)return i-T.length;//匹配成功
    else return 0;//匹配失败
}
void get_next(SString T,int next[]){
    //求模式串T的next函数值并存入数组next
    int i,j;
    i=1;next[1]=0;j=0;
    while(i<T.length)
    {
        if(j==0||T.ch[i]==T.ch[j])
        {
            ++i;++j;next[i]=j;
        }
        else j=next[j];
    }
}
/*void get_nextval(SString T,int nextval[]){
    //求模式串T的next函数修正值并存入数组nextval
    int i,j;
    i=1;nextval[1]=0;j=0;
    while(i<T.length)
    {
        if(j==0||T.ch[i]==T.ch[j])
        {
            ++i;++j;
            if(T.ch[i]!=T.ch[j])nextval[i]=j;
            else nextval[i]=nextval[j];
        }
        else j=nextval[j];
    }

}*/
int main(){
    SString s,t;
    int next[100],k;
    scanf("%s",s.ch+1);
    s.length=strlen(s.ch+1);
    scanf("%s",t.ch+1);
    t.length=strlen(t.ch+1);
    get_next(t,next);
    k=Index_KMP(s,t,next)；
    printf("%d",k);


return 0;
}