本文主要是介绍HDU 2594 Simpsons’ Hidden Talents(KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2594
题目大意：
给两个字符串s1和s2, 求出是s1的前缀并且是s2的后缀的最长的字符串。
分析与总结：
真正理解好KMP算法，这题就是水题。
首先求出s1的失配函数，然后在s2中寻找s1字符串。
在寻找字符串过程中，会有一个状态值j，这个值表示的是当前在s2中已经匹配了多少个s1的字符。 所以，全部匹配完后，最后j的值就是以s2的最后一个字符结尾，和s1的前缀相匹配的最长字符串。也就是所求的答案了。
还有一种方法：
网上有不少题解貌似都是把s1和s2拼接起来成s3，然后求s3自身的next，原理其实是一样的。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int MAXN = 50005;
char s1[MAXN];
char s2[MAXN];
int f[MAXN];void getFail(char *p, int *f){int n=strlen(p);f[0]=f[1]=0;for(int i=1; i<n; ++i){int j=f[i];while(j && p[i]!=p[j]) j=f[j];f[i+1] = p[i]==p[j]?1+j:0;}
}
int find(char *T,char *p,int *f){getFail(p,f);int n=strlen(T);int m=strlen(p);int j=0;for(int i=0; i<n; ++i){while(j && T[i]!=p[j]) j=f[j];if(T[i]==p[j])++j;}return j;
}int main(){while(scanf("%s %s",s1,s2)!=EOF){int x=find(s2,s1,f);if(!x) puts("0");else{int len=strlen(s2);printf("%s %d\n",s2+len-x,x);}}return 0;
}
—— 生命的意义，在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)
这篇关于HDU 2594 Simpsons’ Hidden Talents(KMP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
