kmp.cpp

这是KMP字符串匹配算法的实现代码

#include <stdio.h>
#include <stdlib.h>
void get_next(char *p,int *next)
{
     int j,k;
     j=1;k=0;next[j]=0;
     while(j<p[0])
     {
      if(k==0||p[j]==p[k])
      {
      ++j;++k;
      if(p[j]!=p[k])next[j]=k;
      else next[j]=next[k];
      }
      else
          k=next[k];       
     }
}
int get_input(char *s,char *p)//返回模式串的长度 
{
    printf("输入主串,以#结尾：");
    int i=1;
    do{
        scanf("%c",&s[i]);
        }while(s[i++]!='#');
    s[0]=i-2;//将字符串的长度放到s[0]中
    getchar();//fflush(stdin);
    printf("输入模式串，以#结尾:");
    i=1;
    do{
        scanf("%c",&p[i]);
        }while(p[i++]!='#');
    p[0]=i-2;//将字符串的长度放到p[0]中
    return p[0];
     
}
 
int main()
{
    char s[1001];
    char p[21];
    int *next;
    int length;
    length=get_input(s,p)+1;
    next=(int*)malloc(length*sizeof(int));
    printf("%d,%d\n",s[0],p[0]);
    get_next(p,next);
    //for(int i=1;i<=length-1;i++)
	//printf("%d ",next[i]);
	//开始KMP算法
    int i,j;
    i=1,j=1;
    while(i<=s[0]&&j<=p[0])
    {
    if(j==0||s[i]==p[j]){i++;j++;}
    else j=next[j];
    }
    if(j>p[0]) 
    {          length=i-j+1;
               printf("可以匹配，如下:\n");
               for(i=1;i<=s[0];i++)printf("%c",s[i]);printf("\n");
               for(i=1;i<length;i++)printf(" ");
               for(j=1;j<=p[0];j++)printf("%c",p[j]);printf("\n");
                      
               }
    else printf("不能匹配！"); 
    system("pause");
           
}