HDU 2594 Simpsons’ Hidden Talents(KMP求s1前缀和s2后缀相同部分)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2594

题目大意:给两串字符串s1,s2,,找到最长子串满足既是s1的前缀又是s2的后缀,输出子串,及相应长度。

解题思路:这题是不是跟POJ 2752很像,没错,我们只要将s1、s2合并,不断递归直到找到长度小于等于s1、s2的公共前后缀即可。

代码

 #include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+; int nxt[N];
char s1[N],s2[N]; void getnext(char *p,int m){
int i,j;
i=,j=nxt[]=-;
while(i<m){
while(j!=-&&p[i]!=p[j])
j=nxt[j];
nxt[++i]=++j;
}
} int main(){
while(~scanf("%s",s1)){
scanf("%s",s2);
int m=strlen(s1),n=strlen(s2);
int cnt=m;
//合并s1,s2求nxt数组
for(int i=;i<n;i++){
s1[cnt++]=s2[i];
}
s1[cnt]='\0';
getnext(s1,cnt);
int ans=nxt[cnt];
//s1、s2合并后公共前后缀长度可能大于s1或s2原来的长度,所以要回溯一下找到长度刚好小于s1、s2的公共前后缀
while(ans!=-){
if(ans<=m&&ans<=n)
break;
ans=nxt[ans];
}
if(ans>){
for(int i=;i<ans;i++){
printf("%c",s1[i]);
}
printf(" %d\n",ans);
}
else
printf("%d\n",ans);
}
return ;
}
上一篇:struts分页实现


下一篇:hdu 2594 Simpsons’ Hidden Talents(扩展kmp)