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的前缀，或者b的后缀加上a的前缀，使得到的字符串最短。A+B或 B+A，千万少算了。

思路：

      KMP模板，然后先把b串当模式串与a串比较得到 j 的的位置x，再把a串当模式串与b串比较得到 j 的位置y，如果x = y，说明到j的位置相等，然后比较a,b的长度，谁短先输出谁；如果x > y，先输出a串,再输出相应 j 位置后的b串；如果x < y，先输出 b 串，在输出相应位置 j 后的a串。

    一开始忘了限制返回  j 的条件，所以WA了一次。

代码：

#include<stdio.h>
#include<string.h>
char a[1000010],b[1000010];
int next[100010];
int len1,len2,len;
void get_next(char str[])
{
	int i,j;
	i=1;
	j=0;
	len=strlen(str);
	while(i<len)
	{
		if(j==0&&str[i]!=str[j])
		{
			next[i]=0;
			i++;
		}
		else if(j>0&&str[i]!=str[j])
		{
			j=next[j-1];
		}
		else
		{
			next[i]=j+1;
			i++;
			j++;
		}
	}
}
int kmp(char str1[],char str2[])
{
	int i,j;
	get_next(str2);
	i=0;
	j=0;
	len1=strlen(str1);
	len2=strlen(str2);
	while(i<len1&&j<len2)
	{
		if(j==0&&str2[j]!=str1[i])
		{
			i++;
		}
		else if(j>0&&str2[j]!=str1[i])
		{
			j=next[j-1];
		}
		else
		{
			i++;
			j++;
		}
	}
	if(i>=len1)
		return j;
	return 0;
}
int main()
{
	int x,y;
	while(scanf("%s%s",a,b)!=EOF)
	{
		x=kmp(a,b);
		y=kmp(b,a);
		if(x==y)
		{
			if(strcmp(a,b)>0)
			{
				printf("%s",b);
				printf("%s",a+x);
			}
			else
			{
				printf("%s",a);
				printf("%s",b+x);
			}
		}
		else if(x>y)
		{
			printf("%s",a);
			printf("%s",b+x);
		}
		else
		{
			printf("%s",b);
			printf("%s",a+y);
		}
		printf("\n");
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
	}
	return 0;
 }