hdu 1867 A + B for you again

A + B for you again

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

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 sdfgasdf ghjk

Sample Output

asdfgasdfghjk

/*开始没理解题意阿弥陀佛施主我太想呕吐了原来可以把前面的接到后面去郁闷没考虑到这点原来这就是最短的意识然后还得按最小字典
序输出只要写2个kmp即可让模式串在主串中搜索搜索到最后返回一个j就是相同的数量我们要把2个串分别当一次模式串找到j大的就是重复多的
下面我写的有点复杂了下面的函数都是重复的本来可以合成一个函数的*/

#include<stdio.h>
#include<string.h>
char a[100005];
char b[100005];
int next1[100005];
int next2[100005];
int d1,d2;
void get_next1()
{
	int i=1,j=0;
	next1[1]=0;
	while(i<d2)
	{
		if(j==0||b[i]==b[j]) {i++;j++;next1[i]=j;}
		else j=next1[j];
	}
}
void get_next2()
{
	int i=1,j=0;
	next2[1]=0;
	while(i<d1)
	{
		if(j==0||a[i]==a[j]) {i++;j++;next2[i]=j;}
		else j=next2[j];
	}
}
int KMP1()
{
	int i=1,j=1;
	while(i<=d1)
	{
		if(j==0||a[i]==b[j]) {i++;j++;}
		else j=next1[j];
	}
	return j-1;
}
int KMP2()
{
	int i=1,j=1;
	while(i<=d2)
	{
		if(j==0||b[i]==a[j]) {i++;j++;}
		else j=next2[j];
	}
	return j-1;
}
int main()
{
	int cnt,flag,ans1,ans2;
	while(scanf("%s",a+1)!=EOF)
	{
		cnt=0;flag=0;
		scanf("%s",b+1);
		d1=strlen(a+1);
		d2=strlen(b+1);
		get_next1();
		ans1=KMP1();//a做主串
		get_next2();
		ans2=KMP2();
		//  printf("ans1=%d,ans2=%d\n",ans1,ans2);
		if(ans1>ans2)
		{
			printf("%s%s\n",a+1,b+1+ans1);
		}
		else if(ans1<ans2)
		{
			printf("%s%s\n",b+1,a+1+ans2);
		}
		else
		{
			if(strcmp(a+1,b+1)>0)
				printf("%s%s\n",b+1,a+1+ans1);
			else  printf("%s%s\n",a+1,b+1+ans1);
		}
	}
	return 0;
}