算法题：HDU 2594 Simpsons’ Hidden Talents（KMP）

算法题：HDU 2594 Simpsons’ Hidden Talents（KMP）2014-03-17 csdn博客 shuangde800链接：

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];intf[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
",s2+len-x,x）;}}return 0;}