KMP改进算法
作者:
gzcoder
,
2021-10-14 10:31:33
,
所有人可见
,
阅读 264
#include <iostream>
#include<string>
using namespace std;
#define MAXSIZE 50
int Index_BF(string s,string t,int pos)
{
int i=pos,j=0;
while(i <= s.length()-1 && j <= t.length()-1)
{
if(s[i] == t[j])i++,j++;
else i=i-j+1,j=0;
}
if(j > t.length()-1)return i-t.length();
return -1;
}
void GetNext(int next[],string t)
{
int j=0,k=-1;
next[0]=-1;
while(j<t.size()-1)
{
if(k == -1 || t[j] == t[k])
{
j++;
k++;
if(t[j] != t[k])
next[j]=k;
else
next[j]=next[k];
}else
k=next[k];
}
}
int Index_KMP(string s,string t)
{
int next[MAXSIZE];
int i=0,j=0;
GetNext(next,t);
while(i < (int)s.length() && j < (int)t.length())
{
if(j==-1 || s[i] == t[j]){
i++;
j++;
}
else
j=next[j];
}
if(j >= (int)t.length()){
return (i-t.length());
}
else
return -1;
}
int main()
{
string s,t;
int pos;
cin>>s>>t;
cout<<Index_KMP(s,t);
return 0;
}