题意：
就是求str1 的最长后缀与 str2 的最长前缀。使得 str1+str2 的长度最小，并且字典序最小。
分析：
利用kmp 求出最长相同的后缀和前缀。在利用串比较函数比较最小字典序。具体可以参考代码。
code
1
#include<iostream>
2using namespace std;
3
4const int maxn=100005;
5char a[maxn],b[maxn];
6int next_a[maxn],next_b[maxn];
7
8void Getnext(char *str,int next[])
9
{
10
int j=1,k=0;
11
12 next[0]=-1;
13 next[1]=0;
14 while(str[j])
15
{
16 if(str[j]==str[k])
17 {
18 next[j+1]=k+1;
19 k++;
20 j++;
21
}
22 else if(k==0)
23 {
24 next[j+1]=0;
25 j++;
26 }
27 else k=next[k];
28 }
29
}
30
31int KMPIndex(char *str1,char *str2,int next[])
32{
33 int i,j;
34
35 i=j=0;
36 while(str1[i])
37 {
38 if(str1[i]==str2[j])
39 {
40 i++;
41 j++;
42 }
43 else if(j==0)i++;
44 else j=next[j];
45 }
46 return j;
47}
48
49int main()
50{
51 int k1,k2;
52 while(EOF!=scanf("%s %s",a,b))
53 {
54 Getnext(a,next_a);
55 Getnext(b,next_b);
56 k1=KMPIndex(a,b,next_b);
57 k2=KMPIndex(b,a,next_a);
58
59 if(k1==k2)
60 {
61 if(strcmp(a,b)<=0)
62 printf("%s%s\n",a,b+k1);
63 else
64 printf("%s%s\n",b,a+k1);
65 }
66 else if(k1<k2)
67 printf("%s%s\n",b,a+k2);
68 else
69 printf("%s%s\n",a,b+k1);
70 }
71 return 0;
72}
73
74