/*
*作者JunyiSun @ CCNU
*E-MAIL:CCNUSJY@GMAIL.COM
*KMP算法C代码描述
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_S 101 /*主串的长度最大值为100*/
#define MAX_P 21 /*模式串的长度最大值为20*/
char s[MAX_S],p[MAX_P]; /*s为主串，p为模式串*/
int nextv[MAX_P]; /*p的nextv数组*/
void init_nextv()
{
int i=0,j=-1;
int p_len; /*模式串的长度*/
p_len=strlen(p);
nextv[0]=-1;
while(i<p_len-1){
if(j==-1 || p[i]==p[j]){
++i;++j;
if(p[i]!=p[j])nextv[i]=j;
else nextv[i]=nextv[j];
}
else j=nextv[j];
}
}
int kmp()
{
int i=0,j=0,s_len,p_len;
s_len=strlen(s);
p_len=strlen(p);
while(i<s_len && j<p_len){
if(j==-1 || s[i]==p[j]){
i++;j++;
}
else j=nextv[j];
}
if(j==p_len)return i-p_len;
else return -1;
}
int main()
{
int index=0;
printf("请输入主串:");
scanf("%s",s);
printf("请输入子串:");
scanf("%s",p);
init_nextv();
index=kmp();
if(index!=-1)
printf("匹配成功，匹配位置%d/n",index);
else
printf("匹配失败/n");
system("pause");
return 0;
}