关于C++程序的kmp算法匹配问题，程序一直运行的有问题，修改了几次，还是有问题，请高手帮帮忙修改下，多

Question

#include<iostream>
#include<string>
using namespace std;
int nextval[255];
int strcmp(string s,string t);
int kmp(string s,string t,int pos);
void get_nextval(string t,int nextval[]);
int main()
{
string s="123456987";
string t;
while(cin>>t)
{
cout<<"在"<<kmp(s,t,1)<<"处匹配成功！"<<endl;
}

for(int i=1;i<t.length();++i)
cout<<nextval[i];
return 0;
}
void get_nextval(string t,int nextval[])
{
int i=0;
nextval[0]=0;
int j=0;
while(i<t.length())
{
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];
}
}
int kmp(string s,string t,int pos)
{
//int next[512];//定义一个数组
get_nextval(t,nextval);//获得数组
int i=0;
i=pos; int j=1;
while(i<=s.length()&&j<=t.length())
{
if(j==0||s[i]==t[j])
{ ++i; ++j;}
else j=nextval[j];
}
if(j>t.length())
return i-t.length();
else
return 0;
}
希望大侠帮帮忙不胜感激，真是修改了好几次，都郁闷透顶了……

Answer 1

问你两个问题...
1.你理解了KMP算法吗？
2.你熟悉C++的string类吗？
你的这几行代码，我实在不想评价了，只能对你说：“多动手吧！”
你的错误太多，只知道照书抄，完全没理解算法的含义，你懂算法思想并不代表你能用代码写出你的思想！

【错误1】书中使用的是SString，是自己定义的一个结构体，结果被你硬生生的换成string类，string[0]是字符串的第一个字符,而SString[0]是字符串长度，SString[1]才是第一个字符...这里面的错误自己去理解吧

【错误2】nextval[0]究竟有什么用？你根本没理解...书中用的是0，我这里给你改成-1...为什么就自己去探究吧...

下面是给你改的代码：
#include<iostream>
#include<string>
using namespace std;
int nextval[255];
int strcmp(string s,string t);
int kmp(string s,string t,int pos);
void get_nextval(string t,int nextval[]);
int main()
{
string s="123456987";
string t;
while(cin>>t)
{
cout<<"在"<<kmp(s,t,0)<<"处匹配成功！"<<endl;//改动1
}

for(int i=1;i<t.length();++i)
cout<<nextval[i];
return 0;
}
void get_nextval(string t,int nextval[])
{
int i=1;
nextval[0]=-1; //改动2
nextval[1]=0; //改动3
int j=0;
while(i < t.length())
{
if(j==-1||t[i]==t[j]) //改动4
{
++i; ++j;
if(t[i]!=t[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else j=nextval[j];
}
}
int kmp(string s,string t,int pos)
{
//int next[512];//定义一个数组
get_nextval(t,nextval);//获得数组
int i=0;
i=pos; int j=0; //改动5
while(i < s.length()&&j < (int)t.length()) //改动6
{
if(j==-1||s[i]==t[j]) //改动7
{ ++i; ++j;}
else j=nextval[j];
}
if(j >= t.length()) //改动8
return i-t.length();
else
return 0;
}
//////////////////////////整个程序自己慢慢消化吧 希望你以后不要再浮于表面的学习