HDU 2594 Simpsons’ Hidden Talents(KMP求s1前缀和s2后缀相同部分)
2024-09-01 08:05:22
题目链接: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 ;
}
最新文章
- IE8,IE10下载的临时文件到哪里去了???
- apache的hadoop升级到CDH hadoop2.0时遇到的问题及解决
- elasticsearch1.0 升级2.2的数据备份和恢复
- 4.PHP内核探索:单进程SAPI生命周期
- Connection to DB
- 初识spring与quartz整合实现定时任务
- 关于在MDK4.5以上版本不能使用JLINK V8的解决办法
- 9.14noip模拟试题
- zf-关于荆州首页鼠标移动到导航栏上去触发的js 显示 问题解决办法
- 《Android进阶》之第七篇 NDK的使用
- ie启动不了的解决办法,win7,win8都可以
- Vue 爬坑之路(十一)—— 基于 Nuxt.js 实现服务端渲染(SSR)
- laravel 多条件查询
- Yarn篇--搭建yarn集群
- eclipse编写连接MySQL的简单动态网页
- windows下安装 mysql 8.0 以上版本以及遇到的问题
- matlab中CRC的函数使用
- lsass.exe占用cpu 解决方法
- js的模块化
- ES7: 展开语法spread syntax: