24 lines
489 B
C++
24 lines
489 B
C++
int kmp(string a1,string a2)
|
|
{
|
|
int n=a1.size(),m=a2.size();
|
|
//cout<<"n="<<n<<" m="<<m<<endl;
|
|
string s=a1 + '#' + a2;
|
|
//cout<<s<<endl;
|
|
vector<int> pi(s.size());
|
|
for (int i=n;i<s.size();i++)
|
|
{
|
|
int len=pi[i-1];
|
|
while(len != 0 && s[i] != s[len]){
|
|
len=pi[len-1];
|
|
}
|
|
//cout<<"len="<<len<<endl;
|
|
//cout<<"pi["<<i<<"]="<<pi[i]<<endl;
|
|
if(s[i] == s[len]){
|
|
pi[i] = ++len;
|
|
//cout<<"pi["<<i<<"]="<<pi[i]<<endl;
|
|
if(pi[i] == n) return i - n * 2;
|
|
}
|
|
}
|
|
return -1;
|
|
}
|