題目大意，給定兩個字符串，若一個字串的前綴是另一個字串的後綴，則可以合並。要求合並後的字串首先要盡可能短，然後要按字典序盡可能的短；
思路：兩個字串按先後順序不同可以有兩種組合，對與每種組合得到KMP算法的next數組，next[len]就是兩個字串可以合並的長度；
[cpp]
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define min(a,b) a<b?a:b
using namespace std;
char s[200005],a[100005],b[100005];
int next[200005];
int KMP(int len,int n)
{
int i=0,j=-1;
next[0]=-1;
while(i<n){
if(j==-1||s[i]==s[j]){
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
while(next[n]>len){
n=next[n];
}
return next[n];
}
int main()
{
while(scanf("%s%s",a,b)!=EOF){
int len1=strlen(a);
int len2=strlen(b);
strcat(strcpy(s,a),b);
int ans1=KMP(min(len1,len2),len1+len2);//第一個參數為可以合並的最大長度
strcat(strcpy(s,b),a);
int ans2=KMP(min(len1,len2),len1+len2);
int i;
if(ans1>ans2){
for(i=0;i<len2;i++)printf("%c",b[i]);
for(i=ans1;i<len1;i++)printf("%c",a[i]);
}
else if(ans2>ans1){
for(i=0;i<len1;i++)printf("%c",a[i]);
for(i=ans2;i<len2;i++)printf("%c",b[i]);
}
else{
if(strcmp(a,b)>0){
for(i=0;i<len2;i++)printf("%c",b[i]);
for(i=ans1;i<len1;i++)printf("%c",a[i]);
}
else{
for(i=0;i<len1;i++)printf("%c",a[i]);
for(i=ans2;i<len2;i++)printf("%c",b[i]);
}
}
printf("\n");
}
return 0;
}
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define min(a,b) a<b?a:b
using namespace std;
char s[200005],a[100005],b[100005];
int next[200005];
int KMP(int len,int n)
{
int i=0,j=-1;
next[0]=-1;
while(i<n){
if(j==-1||s[i]==s[j]){
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
while(next[n]>len){
n=next[n];
}
return next[n];
}
int main()
{
while(scanf("%s%s",a,b)!=EOF){
int len1=strlen(a);
int len2=strlen(b);
strcat(strcpy(s,a),b);
int ans1=KMP(min(len1,len2),len1+len2);//第一個參數為可以合並的最大長度
strcat(strcpy(s,b),a);
int ans2=KMP(min(len1,len2),len1+len2);
int i;
if(ans1>ans2){
for(i=0;i<len2;i++)printf("%c",b[i]);
for(i=ans1;i<len1;i++)printf("%c",a[i]);
}
else if(ans2>ans1){
for(i=0;i<len1;i++)printf("%c",a[i]);
for(i=ans2;i<len2;i++)printf("%c",b[i]);
}
else{
if(strcmp(a,b)>0){
for(i=0;i<len2;i++)printf("%c",b[i]);
for(i=ans1;i<len1;i++)printf("%c",a[i]);
}
else{
for(i=0;i<len1;i++)printf("%c",a[i]);
for(i=ans2;i<len2;i++)printf("%c",b[i]);
}
}
printf("\n");
}
return 0;
}
