数据结构 字符串 模式匹配问题 KMP算法

Question

//头文件定义为：
#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 Index(SString S,SString T,int pos)
{ //按照普通匹配查找方式查找模式串
int i=pos;
int j=1,k=0;
while(i<=S[0] && j<=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<T[0])
{
if(j==0 || T[i-1]==T[j-1])
{
++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<T[0])
{
if(j==0 || T[i-1]==T[j-1])
{
++i;
++j;
if(T[i-1]!=T[j-1])
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<=S[0] && j<=T[0])
{
if(j==0 || S[i]==T[j])
{
++i;
++j;
}
else
{
j=next[j];
}

}
if(j>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);

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<=strlen(T);i++)
printf("%d",next[i]);

get_nextval(T,nextval);
printf("\n得到T的nextval[]序列为:");
for(i=1;i<=strlen(T);i++)
printf("%d",nextval[i]);
printf("\n");

if(k2=Index_KMP(S,T,pos,next))
printf("匹配成功!\nKMP算法得模式串位置：%d\n",k2);
else
printf("没有找到，匹配失败!");
}
为什么可以输出NEXT值，但是就是找不到匹配呢？
求纠正啊！！！急啊！！！帮帮忙！！！看看！！！

Answer 1

你的程序本身思路没有错，但错在以下几点：
1.在程序中有字符串S和T，你用S[0]代表字符串的长度，但S是字符串，S[0]是长度吗？
2.在main函数中，你输入的S和T都是用gets(S)或gets(T),那么它们都是以下标0开头的，你应该要进行处理，使它以下标1作为开头（可以这样gets(&S[1]); 然后S[0] = strlen(&S[1]) + '0';在用S[0]作为长度的时候，把它从字符变成数字就行了)。

Answer 2

wqewqeqwr3r43wr追问

来混财富值么？？？童鞋。。。我用追问赏给你。。。。