KMP算法

来自数据结构书 #include<iostream> #include<math.h> #include<memory.h> #include<stdlib.h> using namespace std; string s,t; void GetNext(string t,int next[]) { int j,k; j=0;k=-1; next[0]=-1; while(j<t.size()) { if(k==-1||t[j]==t[k])//k为-1或比较的字符相等时 { j++; k++; if(t[j]!=t[k]) next[j]=k; else next[j]=next[k]; } else k=next[k]; } } int KMP(string s,string t) { int next[t.size()],i=0,j=0; GetNext(t,next); int x,y; x=s.size(); y=t.size(); while(i<x&&j<y) { if(j==-1||s[i]==t[j]) { i++; j++; } else j=next[j]; } if(j>=t.size()) return(i-t.size()); else return -1; } int main() { while(cin>>s>>t) { cout<<KMP(s,t); } return 0; }