题意：求str1 的最长后缀与str2的最长前缀，使得str1 + str2 的长度最小，并且字典序最小，str1 和str2 可交换。

分析：求最长后缀和最长前缀时，自然会想到kmp算法。在此题中，next[i] 表示以i为结尾的字串与开头同样长度的子串匹配的长度。在求next时，我将两个字符串进行了合并，但要注意的是，合并时要在两个字符串之间加上一个字符，不然在合并后求next时会出错（例如abcbcbca bcbcbc）。求出两次合并后最后一个字符的next值，即为最长前缀，输出时把这部分去掉就可以了。具体实现请参考代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
char str1[N], str2[N], str11[N*2], str22[N*2], s[N*2];
int next[N*2];
char* Merge(char *s1, char *s2)
{
    int i, j;
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    strcpy(s, s1);
    s[len1] = ‘.‘;
    for(i = len1 + 1, j = 0; j < len2; i++, j++)
        s[i] = s2[j];
    s[i] = ‘\0‘;
    return s;
}

int get_next(char *a)
{
    int i, j = 0;
    int len = strlen(a);
    for(i = len - 1; i >= 0; i--)
        a[i+1] = a[i];
    next[1] = 0;
    for(i = 2; i <= len; i++)
    {
        while(j > 0 && a[i] != a[j+1])
            j = next[j];
        if(a[i] == a[j+1])
              j++;
        next[i] = j;
    }
    return next[len];
}

int main()
{
    int i;
    while(~scanf("%s%s",str1, str2))
    {
        strcpy(str11, Merge(str1, str2));
        int p = get_next(str11);
        strcpy(str22, Merge(str2, str1));
        int q = get_next(str22);
        if(p > q) //sdfg  asdf
            printf("%s%s",str2, str1 + p);
        else if(p < q) //asdf sdfg
            printf("%s%s",str1,str2+q);
        else
        {
            if(strcmp(str11, str22) < 0)
                printf("%s%s",str1,str2+p);
            else if(strcmp(str11, str22) > 0)
                printf("%s%s",str2,str1+p);
            else
                printf("%s",str1);
        }
        printf("\n");
    }
    return 0;
}

下面的代码是对上面的优化，节省了一部分内存。

#include<stdio.h>
#include<string.h>
const int N = 1e5 + 10;
char str1[N], str2[N], s[N*2];
int next[N*2];

void get_next(char *a)
{
    int i, j = 0;
    int len = strlen(a+1);
    next[1] = 0;
    for(i = 2; i <= len; i++)
    {
        while(j > 0 && a[i] != a[j+1])
            j = next[j];
        if(a[i] == a[j+1])
              j++;
        next[i] = j;
    }
}

int get_Max_len(char *s1, char *s2)
{
    int i, j;
    int len1 = strlen(s1 + 1);
    int len2 = strlen(s2 + 1);
    int lens = len1 + len2 + 1;
    for(i = 1; i <= len1; i++)
        s[i] = s1[i];
    s[len1 + 1] = ‘.‘;
    for(i = 1, j = len1 + 2; i <= len2; i++, j++)
        s[j] = s2[i];
    s[j] = ‘\0‘;
    get_next(s);
    return next[lens];
}
int main()
{
    int i;
    while(~scanf("%s%s",str1 + 1, str2 + 1))
    {
        int p = get_Max_len(str1, str2);
        int q = get_Max_len(str2, str1);
        //printf("%d %d\n",p,q);
        if(p > q) //sdfg  asdf
            printf("%s%s",str2+1,str1+p+1);
        else if(p < q) //asdf sdfg
            printf("%s%s",str1+1, str2+q+1);
        else
        {
            if(strcmp(str1+1, str2+1) < 0)
                printf("%s%s",str1+1,str2+1+p);
            else if(strcmp(str1+1, str2+1) > 0)
                printf("%s%s",str2+1,str1+p+1);
            else
                printf("%s",str1+1);
        }
        printf("\n");
    }
    return 0;
}

有一点我没搞明白，最后输出时，单个字符的输出超时，输出字符串就AC了。