hdoj2594(kmp算法next数组的应用)
2024-09-01 09:56:27
题目链接:https://vjudge.net/problem/HDU-2594
题意:给定两个字符串s1、s2,求s1的前缀和s2的后缀的最长公共部分。
思路:
将s1和s2连接后求nex数组即可,当公共部分超过s1、s2长度的最小值时,输出最小值。
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn=1e5+;
int len1,len2,len,Min,nex[maxn],ans;
char s1[maxn],s2[maxn]; void get_next(){
int j;
j=nex[]=-;
for(int i=;i<len;++i){
while(j>-&&s1[i]!=s1[j+]) j=nex[j];
if(s1[i]==s1[j+]) ++j;
nex[i]=j;
}
} int main(){
while(~scanf("%s%s",s1,s2)){
len1=strlen(s1);
len2=strlen(s2);
Min=min(len1,len2);
strcat(s1,s2);
len=len1+len2;
get_next();
if(nex[len-]+>Min) ans=Min;
else ans=nex[len-]+;
if(ans){
for(int i=;i<ans;++i)
printf("%c",s1[i]);
printf(" ");
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 奶牛通讯 usaco 网络流
- jQuery查看dom元素上绑定的事件列表
- Ubuntu上glibc CVE-2015-7547漏洞的POC验证和修复
- apple
- linux学习第一天(X window 及 语系查询设置)
- 了解 : Odata 的 $filter
- JqGrid 显示表格
- 没搞懂的package.json
- IPv6简介
- React JS和React-Native学习指南
- Spring NoSQL
- weblogic服务目录迁移记录
- Linux(一)——认识Linux
- android 学习之rxjava
- Linux 查看是64位还是32位
- composer应用
- body-parser小解
- 2018,重新开始学习DotNetCore
- AtCoder Regular Contest 093 E: Bichrome Spanning Tree(生成树)
- EIGRP-3-EIGRP的多参数度量