#include <iostream> #include <string> using namespace std; int KMP(string ,string ); void GetNext(string , int next[]); int main() { string s,t; while(cin>>s>>t) cout<<KMP(s,t)<<endl; return 0; } void GetNext(string t , int next[]) { int j=0,k=-1; next[0]=-1; while(j<t.size()-1 ) { if(k==-1 || t.at(j)==t.at(k)) { ++j,++k; next[j]=k; } else k=next[k]; } } int KMP(string s,string t) { int *next=new int[t.size()]; GetNext(t,next); int i=0,j=0; while(i<(int)s.size() && j<(int)t.size()) { if(j==-1 || s.at(i)==t.at(j)) ++i,++j; else j=next[j]; } delete [] next; if(j==t.size()) return i-j; else return -1; }
仙子啊