//求最长相同的串a后缀和串b的前缀(或者是最长相同的串b后缀和串a的前缀),
//进行合并,得到长度最短的a+b,且字典序最小
//解题思路:
//KMP的运用,利用KMP求出最长相同的串a后缀和串b的前缀 和 最长相同的串b后缀和串a的前缀,
//然后按较长的进行输出
#include<stdio.h> #include<string.h> char s1[100002],s2[100002]; int next1[100002],next2[100002]; void get(int next[],char s[]) { int len=strlen(s); int j,i; j=-1;i=0;next[0]=-1; while(i!=len) { if(j==-1||s[i]==s[j]) { next[++i]=++j; } else j=next[j]; } } int KMP(int next[],char s1[],char s2[]) { int i,j; int len2; j=0;i=0; len2=strlen(s2); while(i!=len2)//以i之后的为后缀与s1的前缀比较 { if(s2[i]==s1[j])//匹配成功 { i++;j++; } else //匹配不成功 { j=next[j]; if(j==-1){j=0;i++;}//只有next[0]=-1,所以j=0; } } return j; } int main() { int len1,len2; while(scanf("%s%s",s1,s2)!=-1) { get(next1,s1); len1=KMP(next1,s1,s2); get(next2,s2); len2=KMP(next2,s2,s1); if(len1==len2) { if(strcmp(s1,s2)<0) printf("%s%s\n",s1,s2+len1); else printf("%s%s\n",s2,s1+len1); } else if(len1<len2) { printf("%s%s\n",s1,s2+len2); } else { printf("%s%s\n",s2,s1+len1); } } return 0; }