hdu1867A + B for you again（kmp）

矫情吗；* 2022-08-21 08:45 4阅读 0赞

# A + B for you again #

**Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 5925    Accepted Submission(s): 1469**

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

Author

Wang Ye

Source

[2008杭电集训队选拔赛——热身赛][2008]

Recommend

lcy   |   We have carefully selected several similar problems for you:   [1866][]  [1277][]  [1358][]  [1865][]  [2057][]

题意：

将两个字符串合并将匹配的字符串删去按字符串的字典数小的输出；

\#include<stdio.h>  
\#include<string.h>  
int next\[100005\];  
void NEW(char b\[\])//子串的next  
\{  
    int i,q=0;  
    next\[0\]=0;  
    int m1;  
    m1=strlen(b);  
    for(i=1;i<m1;i++)  
    \{  
        while(q>0&&b\[q\]!=b\[i\])  
            q=next\[q-1\];  
        if(b\[q\]==b\[i\])  
            q++;  
        next\[i\]=q;  
    \}  
\}  
int xiao(char a\[\],char b\[\])  
\{  
    int i;  
    NEW(b);  
    int q=0;  
    int m=strlen(a);  
    for(i=0;i<m;i++)  
    \{  
        while(q>0&&a\[i\]!=b\[q\])  
            q=next\[q-1\];  
        if(a\[i\]==b\[q\])  
            q++;  
    \}  
    return q;  
\}//母函数模板。  
int main()  
\{  
    char a\[100005\],b\[100005\];  
    while(~scanf("%s%s",a,b))  
    \{  
        int m,n;  
        m=xiao(a,b);  
        n=xiao(b,a);//比较出那个匹配的最少。  
        if(m==n)//  
        \{  
            if(strcmp(a,b)>0)//相等的会看哪个在前面使字典数较小。  
           \{  
              printf("%s",b);  
              printf("%s\\n",a+m);  
  
  
           \}  
            else  
            \{  
               printf("%s",a);  
                printf("%s\\n",b+m);  
           \}  
        \}  
       else if(m>n)//比较出那个匹配使字符串较短。  
        \{  
             printf("%s",a);  
            printf("%s\\n",b+m);  
        \}  
        else  
        \{  
             printf("%s",b);  
            printf("%s\\n",a+n);  
        \}  
    \}  
    return 0;  
\}

[2008]: http://acm.hdu.edu.cn/search.php?field=problem&key=2008%BA%BC%B5%E7%BC%AF%D1%B5%B6%D3%D1%A1%B0%CE%C8%FC%A1%AA%A1%AA%C8%C8%C9%ED%C8%FC&source=1&searchmode=source
[1866]: http://acm.hdu.edu.cn/showproblem.php?pid=1866
[1277]: http://acm.hdu.edu.cn/showproblem.php?pid=1277
[1358]: http://acm.hdu.edu.cn/showproblem.php?pid=1358
[1865]: http://acm.hdu.edu.cn/showproblem.php?pid=1865
[2057]: http://acm.hdu.edu.cn/showproblem.php?pid=2057