hdu 1867 A + B for you again

最新推荐文章于 2024-05-15 16:44:19 发布

acm_JL

最新推荐文章于 2024-05-15 16:44:19 发布

阅读量545

点赞数

分类专栏：字符串和数组

本文链接：https://blog.csdn.net/acm_JL/article/details/50953140

版权

字符串和数组专栏收录该内容

8 篇文章

订阅专栏

本文介绍了一种改进的KMP算法用于解决两个字符串合并的问题，确保合并后的字符串长度最小，且在长度相同时优先选择字典序较小的字符串。通过实例演示算法的应用过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目大意：两个字符串合并成一个，串1的后缀和串2前缀相同部分只出现一次，不固定串1串2，要求合并后串长最小，如果有等串长的两种情况出现，取字典序小的。

算法分析：改进kmp算法求得s1后缀与s2前缀的最大相同长度x，之后输出s1和s2+x

Sample Input

  
  
   
   asdf sdfg
asdf ghjk

Sample Output

 
 
  
    asdfg
  asdfghjk

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int  MAXN= 100010;
char s1[MAXN],s2[MAXN];
int next[MAXN];
void get_nextval(char s[])//求next数组
{
    int i,j;
    i = -1;
    j = 0;
    next[0] = -1;
    int len = strlen(s);
    while(j<len)
    {
        if(i == -1 || s[i] == s[j])
        {
            j++; i++;
            next[j] = i;
        }
        else
            i = next[i];
    }
}

int KMP(char s1[],char s2[])//返回s1后缀和s2前缀的最大相同长度！！！！！，参数的顺序很重要。 
{
    int i,j;
    i = 0;
    j = 0;
    get_nextval(s2);
    int len1 = strlen(s1),len2 = strlen(s2);
    while(i<len1 && j<len2)
    {
        if(j == -1 || s1[i] == s2[j])
        {
            i++; j++;
        }
        else
            j = next[j];
    }
    //kmp改进部分 
    if(i == len1)
    {
        return j;
    }  
    return 0;
}  

int main()
{
    int a,b;
    while(scanf("%s%s",s1,s2) != EOF)
    {
        a = KMP(s1,s2);
        b = KMP(s2,s1);//首先取最短的字符串输出，如果相同，比较字典序即可
        if(a == b)
        {
            if(strcmp(s1,s2)>0)
                printf("%s%s\n",s2,s1+a);
            else
                printf("%s%s\n",s1,s2+a);//s2+a意思是从s2[a]开始输出字符串 
        }
        else if(a>b)
        {
            printf("%s%s\n",s1,s2+a);
        }
        else
            printf("%s%s\n",s2,s1+b);
    }
    return 0;
}