hdu 1867 A + B for you again KMP算法

Problem Description

Generally speaking, there are a lot of problems about strings processing. Now you encounter another such problem. If you get two strings, such as “asdf” and “sdfg”, the result of the addition between them is “asdfg”, for “sdf” is the tail substring of “asdf” and the head substring of the “sdfg” . However, the result comes as “asdfghjk”, when you have to add “asdf” and “ghjk” and guarantee the shortest string first, then the minimum lexicographic second, the same rules for other additions.

 

Input

For each case, there are two strings (the chars selected just form ‘a’ to ‘z’) for you, and each length of theirs won’t exceed 10^5 and won’t be empty.

 

Output

Print the ultimate string by the book.

 

Sample Input

asdf sdfg asdf ghjk

 

Sample Output

asdfg asdfghjk

 

题意：给定两个字符串a和b，现在要将a和b相加，a+b相加规则为找出a最长的后缀等于b的等长前缀，之后结果为a的前面部分+相等部分+b的后面部分，例如：asdf+sdfg=asdfg。相加的时候也可以b+a，输出相加后长度最小的，若存在两者长度相等，则输出字典树较小的。

 思路：由于要得到a+b,和b+a较小的，所以KMP两次；

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int nex[100005];
void getnext(char c[])
{
    int i=0,j=-1;
    nex[0]=-1;
    while(c[i])
    {
        if(j==-1||c[i]==c[j])
            nex[++i]=++j;
        else
            j=nex[j];
    }
}
int kmp(char c1[],char c2[])
{
    int len1=strlen(c1);
    int len2=strlen(c2);
    getnext(c2);
    int j=0,i,maxn=0;
    int flag=0;
    for(i=0;i<len1;i++)
    {
        if(c1[i]==c2[j])
        {
            j++;
            continue;
        }
        if(j==0)
            continue;
        j=nex[j];
        i--;
    }
    return j;
}
int main()
{
    char c1[100005],c2[100005];
    while(~scanf("%s%s",c1,c2))
    {
        int x=kmp(c1,c2);
        int y=kmp(c2,c1);
        if(x==y)
        {
            if(strcmp(c1,c2)>0)
            {
                printf("%s",c2);
                printf("%s",c1+x);
            }
            else
            {
                printf("%s",c1);
                printf("%s",c2+x);
            }
        }
        else if(x<y)
        {
            printf("%s",c2);
            printf("%s",c1+y);
        }
        else
        {
            printf("%s",c1);
            printf("%s",c2+x);
        }
        printf("\n");
    }
}