修改如下 :
//头文件定义为:
#include
#include
#include
//#include
//宏定义:
#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-1;;
return 0;
}
int Index(SString S,SString T,int pos)
{ //按照普通匹配查找方式查找模式串
int i=pos;
int j=1;
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;
char *p;
int pos;
int k1,k2,k;
int i,j;
int next[MAXSTRLEN];
int nextval[MAXSTRLEN];
printf("请输入字符串匹配主串:\n");
p=&S[1];
gets(p);
printf("请输入字符串匹配模式串:\n");
p=&T[1];
gets(p);
printf("您输入的字符串匹配中主串为:\n");
p=&S[1];
puts(p);
printf("您输入的字符串匹配中模式串为:\n");
p=&T[1];
puts(p);
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("没有找到,匹配失败!");
}