Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 2456 Accepted
Submission(s): 929
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=50005; int n,m; int f[maxn]; char s1[maxn],s2[maxn]; void getFail() { int i,j; f[0]=f[1]=0; for(i=1;i<m;i++) { j=f[i]; while(j && s2[i]!=s2[j]) j=f[j]; f[i+1]=(s2[i]==s2[j]?j+1:0); } } int find() { int i,j=0; getFail(); for(i=0;i<n;i++) { while(j && s1[i]!=s2[j]) j=f[j]; if(s1[i]==s2[j]) j++; }return j; } int main() { int ans; while(~scanf("%s %s",s2,s1)) { n=strlen(s1);m=strlen(s2); ans=find(); if(ans) printf("%s %d\n",s1+(n-ans),ans); else printf("0\n"); } return 0; }
HDU 2594 kmp算法变形,布布扣,bubuko.com
原文：http://www.cnblogs.com/xiong-/p/3628682.html