HDU 1867 A + B for you again（KMP算法的应用）

浏览数：22 / 时间：2015年06月08日

A + B for you again

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4496 Accepted Submission(s): 1157

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

题意讲解： 给你两个字符串 s1，s2让你把它们，连接起来前后相同的重合一起，不再输出；

连接规则：

         假设     s1 + s2  能匹配的长度为 len1 ；

                  s2 + s1 能匹配的长度为  len2 ；

如果 len1 = len2 判断谁在前就要看谁得字典序小了，当然小的在前

如果 len1 > len2   输出匹配后的字符串 s1+s2

如果 len1 < len2   输出匹配后的字符串 s2+s1

所以AC代码如下：略长

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
const int N = 1e5+10;
char s1[N],s2[N];
int next[2][N],len1,len2;
int x1,x2;
void solve1(int len1)//寻找第一个字符串的next数组
{
   int i = 0;
   int j = -1;
   next[0][0] = -1;
   while(i<len1)
   {
       if(j== -1 || s1[i] == s1[j])
       {
           ++i;
           ++j;
           next[0][i] = j;
       }
       else
           {
              j = next[0][j];
           }
   }
}
void solve2(int len2)//寻找第二个字符串的next数组
{
   int i = 0;
   int j = -1;
   next[1][0] = -1;
   while(i<len2)
   {
       if(j== -1 || s2[i] == s2[j])
       {
           ++i;
           ++j;
           next[1][i] = j;
       }
       else
           {
              j = next[1][j];
           }
   }
}
int solve(char *s3,char *s4,int len,int x) //xx：表示字符串s3和s4匹配时，是从s3的第xx个开始匹配的
{
   int j=0,i=0;
   int  xx=0;
     while(i<len)
       {
            if(j==-1 || s3[i] == s4[j])
            {
                i++;
                j++;
            }
            else
            {
               j = next[x][j];
               xx=i-j;
            }
       }
       return xx;
}
int main()
{
   while(~scanf("%s %s",s1,s2))
   {
       memset(next,-1,sizeof(next));
       len1 = strlen(s1);
       len2 = strlen(s2);
       solve1(len1);
       solve2(len2);
       int x1 = solve(s1,s2,len1,1);
       int x2 = solve(s2,s1,len2,0);
       //判断能匹配字符串的长度
       int xx1 = len1 - x1; 
       int xx2 = len2 - x2;
       //当s1在前或者s2在前连接的字符串总长度是相同的，则要按照字典序小的在前，
       //例如：s1：abcefg s2：efgabc  都能匹配对方三个，所以要按照字典序abcefg 在前；
       if(xx1 == xx2)
       {
           if(strcmp(s1,s2)<0)
           {
               for(int i=0; i<x1; i++)
                      printf("%c",s1[i]);
                 printf("%s\n",s2);
           }
           else
           {
                  for(int i=0; i<x2; i++)
                      printf("%c",s2[i]);
                 printf("%s\n",s1);
           }
       }
       //接下来就看，谁能匹配谁的多了，xx1 表示s2匹配s1 的长度，xx2表示  s1 匹配 s2的长度；
       //例如s1: abcdef s2: hjabcd  ;这时s2，在前先输出；反之s1在前；
      else if(xx1 > xx2)
       {
              for(int i=0; i<x1; i++)
               printf("%c",s1[i]);
              printf("%s\n",s2);

       }
       else
       {
                   for(int i=0; i<x2; i++)
                      printf("%c",s2[i]);
                 printf("%s\n",s1);
       }
   }
 return 0;
}
 