#include<iostream>
#include<string>
using namespace std;
int index_BF(string s,string t,int pos)
{
int j=0,i=pos;
while(i<s.length()&&j<t.length()) {
if(s[i]==t[j]) {
i++;
j++;
}
else {
i=i-j+1;
j=0;
}
}
if(j==t.length()) return i-j;
return -1;
}
void getNext(string t,int next[]) {
int j=-1,i=0;
next[0]=-1;
while(i<t.length()-1) {
if(j==-1||t[i]==t[j]) {
i++;
j++;
next[i]=j;
} else {
j=next[j];
}
}
}
void GetNext(string p,int next[])
{
int pLen = p.length();
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
}
int KmpSearch(string s, string p)
{
int next[100];
int i = 0;
int j = 0;
int sLen = s.length();
int pLen = p.length();
GetNext(p,next);
while (i < sLen && j < pLen)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
int index_kmp(string s,string t,int pos)
{
int next[100];
int j=0,i=pos;
GetNext(t,next);
int sLen = s.length();
int tLen = t.length();
for(int x=0; x<tLen; x++)
cout<<next[x]<<" ";
cout << endl;
while(i<s.length()&&j<tLen)
//while(i<s.length()&&j<t.length())
{
if(j==-1||s[i]==t[j]) {
i++;
j++;
} else {j=next[j];}
}
//cout << t.length() << endl;
if(j==t.length()) return i-j;
return -1;
}
int main()
{
string s,t;
while(cin>>s>>t) {
//cout<<"BF:"<<index_BF(s,t,0)<<endl;
cout<<"KMP:\n"<<index_kmp(s,t,0)<<endl;
cout << KmpSearch(s,t) << endl;
}
return 0;
}
想不明白,求解
这两种按你写的是等价的,有报错吗