题目链接: 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+5;
- int len1,len2,len,Min,nex[maxn],ans;
- char s1[maxn],s2[maxn];
- void get_next(){
- int j;
- j=nex[0]=-1;
- for(int i=1;i<len;++i){
- while(j>-1&&s1[i]!=s1[j+1]) j=nex[j];
- if(s1[i]==s1[j+1]) ++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-1]+1>Min) ans=Min;
- else ans=nex[len-1]+1;
- if(ans){
- for(int i=0;i<ans;++i)
- printf("%c",s1[i]);
- printf(" ");
- }
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3273344.html