//头文件定义为：
#include <stdio.h>
//#include <stdlib.h>
#include <string.h>
//#include <malloc.h>
//宏定义：
#define OVERFLOW -2
#define OK 1
#define MAXSTRLEN 255
typedef char SString[MAXSTRLEN+1];
int strLengh(SString S)
{
int m;
for(m=1;S[m]!='\0';m++);
S[0]=m;
return 0;
}
int Index(SString S,SString T,int pos)
{ //按照普通匹配查找方式查找模式串
int i=pos;
int j=1,k=0;
while(i<=(int)S[0] && j<=(int)T[0])
{
if(S[i]==T[j])
{
++i;
++j;
}
else
{
i=i-j+2;
j=1;
}
}
if(j>T[0])
return i-T[0];
else return 0;
}//Index
void get_next(SString T,int next[])
{ //求KMP算法中的next函数值，并存入数组next[]
int i=1;
next[1]=0;
int j=0;
while(i<(int)T[0])
{
if(j==0 || T[i]==T[j])
{
++i;
++j;
next[i]=j;
}
else j=next[j];
}
}//next
int get_nextval(SString T,int nextval[])
{
int i=1;
nextval[1]=0;
int j=0;
while(i<(int)T[0])
{
if(j==0 || T[i]==T[j])
{
++i;
++j;
if(T[i]!=T[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else j=nextval[j];
}
return 0;
}//nextval
int Index_KMP(SString S,SString T,int pos,int next[])
{ //KMP算法的实现过程
int i=pos;
int j=1,k=0;
while(i<=(int)S[0] && j<=(int)T[0])
{
if(j==0 || S[i]==T[j])
{
++i;
++j;
}
else
{
j=next[j];
}
}
if(j>(int)T[0])
return i-T[0];
else return 0;
}//Index_KMP
void main()
{
SString T,S;
int pos;
int k1,k2;
int i,j;
int next[MAXSTRLEN];
int nextval[MAXSTRLEN];
printf("请输入字符串匹配主串：\n");
gets(S);
printf("请输入字符串匹配模式串：\n");
gets(T);
getchar();
printf("您输入的字符串匹配中主串为：\n");
puts(S);
printf("您输入的字符串匹配中模式串为：\n");
puts(T);
getchar();
printf("请您输入起始位置pos：");
scanf("%d",&pos);
strLengh(S);
strLengh(T);
printf("\n----------运用普通算法------------\n");
printf("\n");
if(k1=Index(S,T,pos))
printf("匹配成功!\n普通匹配算法得模式串位置：%d\n",k1);
else
printf("没有找到，匹配失败!\n");
printf("\n----------运用KMP算法------------\n");
get_next(T,next);
printf("得到T的next[]序列为:");
for(i=1;i<=T[0];i++)
printf("%d",next[i]);
get_nextval(T,nextval);
printf("\n得到T的nextval[]序列为:");
for(i=1;i<=T[0];i++)
printf("%d",nextval[i]);
printf("\n");
if(k2=Index_KMP(S,T,pos,next))
printf("匹配成功!\nKMP算法得模式串位置：%d\n",k2);
else
printf("没有找到，匹配失败!");
}
用KMP匹配法
假如我的主串是abcabaasdf
模式串是abcabaa
那么next[j]的值应该是0111232
nextval[j]的值应该是0110132
为什么我的这个程序输出的却是next[j]0111211 nextval[j]0110211
并且用普通匹配法却不能找到匹配
求高手改进啊！！！急啊！谢啦！