题目链接: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 ;
}

最新文章

  1. IE8,IE10下载的临时文件到哪里去了???
  2. apache的hadoop升级到CDH hadoop2.0时遇到的问题及解决
  3. elasticsearch1.0 升级2.2的数据备份和恢复
  4. 4.PHP内核探索:单进程SAPI生命周期
  5. Connection to DB
  6. 初识spring与quartz整合实现定时任务
  7. 关于在MDK4.5以上版本不能使用JLINK V8的解决办法
  8. 9.14noip模拟试题
  9. zf-关于荆州首页鼠标移动到导航栏上去触发的js 显示 问题解决办法
  10. 《Android进阶》之第七篇 NDK的使用
  11. ie启动不了的解决办法,win7,win8都可以
  12. Vue 爬坑之路(十一)—— 基于 Nuxt.js 实现服务端渲染(SSR)
  13. laravel 多条件查询
  14. Yarn篇--搭建yarn集群
  15. eclipse编写连接MySQL的简单动态网页
  16. windows下安装 mysql 8.0 以上版本以及遇到的问题
  17. matlab中CRC的函数使用
  18. lsass.exe占用cpu 解决方法
  19. js的模块化
  20. ES7: 展开语法spread syntax:

热门文章

  1. [USACO4.1]麦香牛块Beef McNuggets 题解报告
  2. 微软.NET Framework cve-2017-8759 复现
  3. 【期望】【P5081】Tweetuzki 爱取球
  4. oracle的sign()函数
  5. Hdu1255 覆盖的面积
  6. php输出控制函数存在的意义
  7. STL源码分析-deque
  8. 题解【bzoj3529 [SDOI2014]数表】
  9. helm 安装prometheus operator 并监控ingress
  10. 2015年IPC网络摄像机技术发展现状分析