串的模式匹配算法：
#include <iostream> #include <cstring> #include <algorithm> #include <string> using namespace std; int Next[1100]; void getNext(string t) { Next[0]=-1; Next[1]=0; int len=0,i=1; while(i<t.length()) { if(len==-1||t[i]==t[len]) { len++; i++; if(t[i]==t[len]) Next[i]=Next[len]; else Next[i]=len; //Next[i]=len; } else len=Next[len]; } } int main() { string s,t; cin>>s>>t; getNext(t); for(int i=0; i<t.length(); i++) cout<<Next[i]<<' '; cout<<endl; int ans=-1; int lent=t.length(),lens=s.length(); for(int i=0,j=0; i<=lens;) { if(j<lent&&j<lens) if(j<0||s[i]==t[j]) { i++; j++; } else { j=Next[j]; } else { if(j==lent) ans=i; break; } } if(ans<0) cout<<"NO"<<endl; else cout<<ans-t.length()<<endl; return 0; }如果 i + next[i - a] < p，如上图，三个椭圆长度相同，根据 next 数组的定义，此时 extend[i] = next[i - a]。 如果 i + next[i - a] > p ,那说明 S[i…p) 与 T[i-a…p-a) 相同，注意到 S[p] != T[p - a] 且 T[p - i] == T[p - a]，也就是说 S[p] != T[p - i]，所以就没有继续往下判断的必要了，我们可以直接将 extend[i] 赋值为 p - i.
#include <iostream> #include <string> using namespace std; int nextval[1000]; int extend[1000]; void getnext(string t) { int a=0,p=0; int lent=t.length(); nextval[0]=lent; for(int i=1; i<lent; i++) { if(i>=p||i+nextval[i-a]>=p) { if(i>=p) p=i; while(p<lent&&t[p]==t[p-i]) p++; nextval[i]=p-i; a=i; } else nextval[i]=nextval[i-a]; } } void getextend(string s,string t) { int a=0,p=0; int lens=s.length(),lent=t.length(); for(int i=0; i<lens; i++) { if(i>=p||i+nextval[i-a]>=p) { if(i>=p) p=i; while(p<lens&&p-i<lent&&s[p]==t[p-i]) p++; extend[i]=p-i; a=i; } else extend[i]=nextval[i-a]; } } int main() { string s,t; cin>>s>>t; getnext(t); getextend(s,t); for(int i=0; i<s.length(); i++) cout<<extend[i]<<' '; cout<<endl; for(int i=0; i<t.length(); i++) cout<<nextval[i]<<' '; return 0; }