参考介绍：点击打开链接 点击打开链接
模板题：hdu2594 （扩展KMP）
http://acm.hdu.edu.cn/showproblem.php?pid=2594
题目大意：给定两个字符串，在第一个字符串中找到一个最大前缀作为第二个字符串的后缀
思路：将S1作为模式串 然后在s2中寻找，求出s1的next数组，nxt[i]:x[i...m-1]与x[0...m-1]的最长公共前缀。同时求出s2的extend数组，extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀
借鉴kuangbin的模板：
#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; /* * 扩展KMP算法 */ //nxt[i]:x[i...m-1]与x[0...m-1]的最长公共前缀 //extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀 int nxt[100050]; int extend[100050]; char s[100050], t[100050]; void pre_EKMP(char x[],int m,int nxt[]) { nxt[0]=m; int j=0; while(j+1<m && x[j]==x[j+1]) j++; nxt[1]=j; int k=1; for(int i=2;i<m;i++) { int p=nxt[k]+k-1; int L=nxt[i-k]; if(i+L<p+1)nxt[i]=L; else { j=max(0,p-i+1); while(i+j<m && x[i+j]==x[j])j++; nxt[i]=j; k=i; } } } void EKMP(char x[],int m,char y[],int n,int nxt[],int extend[]) { pre_EKMP(x,m,nxt); int j=0; while(j<n && j<m && x[j]==y[j]) j++; extend[0]=j; int k=0; for(int i=1;i<n;i++) { int p=extend[k]+k-1; int L=nxt[i-k]; if(i+L<p+1) extend[i]=L; else { j=max(0,p-i+1); while(i+j<n && j<m && y[i+j]==x[j]) j++; extend[i]=j; k=i; } } } int main() { while(cin >> s >> t) { int slen = strlen(s),tlen = strlen(t); EKMP(s,slen,t,tlen,nxt,extend); int ans = 0; for(int i = tlen - 1, j = 0; j < slen; j++, i--) { if(extend[i] == tlen - i) { ans = max(ans, extend[i]); } } if(ans) { for(int i = 0; i < ans; i++) cout << s[i]; cout << " "; } cout << ans <<endl; } return 0; }
