HDU - 1867 A + B for you again (kmp)

我不是女神ヾ 2022-05-19 07:52 146阅读 0赞

#                                    A + B for you again #

### 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，b+a，当前一个字符串的最大后缀和后一个字符串的最大前缀相同时则可合并；a+b与b+a输出长度小的那个，当长度相同时输出字典序小的那个。

**解题思路：**

利用kmp算法求出当前一个字符串判断完时后一个字符串判断到的位置；位置越靠后说明此种情况结合长度最小，若长度相同利用strcmp( )函数判断前一个字符串与后一个字典序的大小。

#include<stdio.h>
    #include<string.h>
    
    int next[100010];
    void get_next(char x[],int lenx)
    {
    	int i,j;
    	j=0;
    	i=1;
    	next[0]=0;
    	while(i<lenx)
    	{
    		if(x[i]==x[j])
    		{
    			next[i]=j+1;
    			i++;
    			j++;
    		}
    		if(j==0&&x[i]!=x[j])
    		{
    			next[i]=0;
    			i++;
    		}
    		if(j>0&&x[i]!=x[j])
    		{
    			j=next[j-1];
    		}
    	}
    }
    int kmp(char p[],char q[])
    {
    	int lenp,lenq;
    	int i,j;
    	lenp=strlen(p);
    	lenq=strlen(q);
    	get_next(q,lenq);
    	i=0;
    	j=0;
    	while(i<=lenp)
    	{
    		if(p[i]==q[j])
    		{
    			j++;
    			if(j==lenq)
    			{
    				if(i==lenp-1)//当前一个数组刚好查找完而且刚好把后一个数组也查找完，			 
    				{				//返回j此时j已经等于lenq输出时只会输出前一个字符了
    					return j;
    				}
    					
    				j=next[j-1];
    			}
    			i++;
    		}
    		//因为有两个地方进行i++了，所以判断了两次，防止i++后又进行判断 
    		if(i==lenp)//当i加过后等于lenp说明前一个字符已经查找完，返回后一个字符位置
    			return j;
    			
    		if(j==0&&p[i]!=q[j])
    			i++;
    			
    		if(i==lenp)
    			return j;
    			
    		if(j>0&&p[i]!=q[j])
    			j=next[j-1];
    	}
    }
    int main()
    {
    	char a[100010],b[100010];
    	int lena,lenb,x,y;
    	int i,j;
    	while(scanf("%s%s",a,b)!=EOF)
    	{
    		lena=strlen(a);
    		lenb=strlen(b);
    		x=kmp(a,b);
    		y=kmp(b,a);
    		if(x<y)
    			printf("%s%s\n",b,a+y);
    		else if(x>y)
    			printf("%s%s\n",a,b+x);
    		else
    		{
    			if(strcmp(a,b)<=0)
    				printf("%s%s\n",a,b+x);
    			else
    				printf("%s%s\n",b,a+y);
    		}
    	}
    	return 0;
    }