串的模式匹配算法

#include<stdio.h>
#define MAXLEN 40 
static int next[MAXLEN];
static int nextval[MAXLEN];
typedef struct{
    char ch[MAXLEN];
    int len;
}SString;

int Index_KMP(SString S,int pos,SString T)
{
    int i=pos,j=1;
    while(i<=S.len-1&&j<=T.len-1)
    {
         if(j==0||S.ch[i]==T.ch[j])
         {
             ++i;
             ++j;
         }
         else
             j=next[j];
    }
    if (j > T.len - 1)
         return i - T.len;
    else
         return 0;
}

void Get_Next(SString T,int next[])
{
    int j=1,k=0;
    next[1]=0;
    while(j<T.len)
    {
         if(k==0||T.ch[j]==T.ch[k])
         {
             ++j;
             ++k;
             next[j]=k;
         }
         else
             k=next[k];
    }
}

void Get_Nextval(SString T, int *next, int nextval[])
{
    int j = 2, k = 0;
    Get_Next(T, next);
    nextval[1] = 0;
    while (j <= T.len - 1)
    {
         k = next[j];
         if (T.ch[j]==T.ch[k])
             nextval[j] = nextval[k];
         else
             nextval[j] = next[j];
         j++;
    }
}

void Print(SString *S)
{
    int i;//实际长度要加1
    for(i=1;i<S->len;i++)
    {
         printf(\"%4c\",S->ch[i]);
    }
}

int main()
{
    SString S,T,S1,T1;
    int i,m,c,n=0;
    printf(\"请输入S串的长度:\");
    scanf(\"%d\",&m);
    S.len=m;
    for(i=0;i<S.len;i++)
    {
    S.ch[i]=getchar();
    }
    printf(\"该串为:  \");
    Print(&S);
    printf(\"\\n请输入T串的长度:\");
    scanf(\"%d\",&m);
    T.len=m;
    for(i=0;i<T.len;i++)
    {
         T.ch[i]=getchar();
    }
    printf(\"该模式串为:\\n\");
    Print(&T);
    Get_Next(T,next);
    printf(\"\\n\");
    printf(\"模式串的next值为:\\n\");
    for (i = 1; i <T.len; i++)
    {
         printf(\"%4d\", next[i]);
    }
    m=Index_KMP(S,n,T);
    printf(\"\\n位置为:%d\\n\",m);
    printf(\"请输入S1串的长度:\");
    scanf(\"%d\", &m);
    S1.len = m;
    for (i = 0;i<S1.len; i++)
    {
         S1.ch[i] = getchar();
    }
    printf(\"该串为:  \");
    Print(&S1);
    printf(\"\\n请输入T1串的长度:\");
    scanf(\"%d\", &m);
    T1.len = m;
    for (i = 0;i<T1.len; i++)
    {
         T1.ch[i] = getchar();
    }
    printf(\"该模式串为:\\n\");
    Print(&T1);
    Get_Nextval(T1,next,nextval);
    printf(\"\\n模式串的nextval值为:\\n\");
    for (i = 1; i <T1.len; i++)
    {
         printf(\"%4d\", next[i]);
    }
    m = Index_KMP(S1, n, T1);
    printf(\"\\n位置为:%d\\n\", m);
    return 0;
}