欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Hdu 2594 Simpsons’ Hidden Talents(Next数组的应用)

程序员文章站 2022-05-02 17:33:10
...

传送门

题意:给你两个字符串s1和s2,它们的长度不超过50000,问你s1的前缀和s2的后缀所能匹配的最大长度,如果无法匹配就输出0,否则就输出这个最大长度的序列,并输出它的长度。

分析:拿到这个题感觉很简单,直接将s2字符串拼接到s1字符串后面,然后用Next[新串的长度]的值不就完了吗?这里注意一个地方,例如:s1:abcabc 和 s2:abc,照刚刚那种思路的话就会输出6 但我们很快发现s2的最大长度也才3,所以其实应该输出的是3,所以其实这个长度是不能超过s1和s2的任意一个字符串的长度的。所以我们就不断地利用Next数组的信息,直到要输出的答案不大于两个串中的任意一个的时候,就输出答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+7;
char s1[maxn<<1],s2[maxn];
int Next[maxn<<1];
int len1,len2,len,ans;

void getNext()
{
    int j = -1,i = 0;
    Next[0] = -1;
    while(i<len)
    {
        if(j==-1||s1[i]==s1[j])
        {
            i++;
            j++;
            Next[i]=j;
        }
        else j = Next[j];
    }
}

void slove()
{
    while(ans>len1||ans>len2) ans=Next[ans];
    if(!ans) printf("0\n");
    else{
        s1[ans]='\0';
        printf("%s %d\n",s1,ans);
    }
}

int main()
{
    while(scanf("%s",s1)!=EOF)
    {
        len1=strlen(s1);
        scanf("%s",s2);
        len2=strlen(s2);
        strcat(s1,s2);
        len=strlen(s1);
        getNext();
        ans = Next[len];
        slove();
    }
    return 0;
}

 

相关标签: Hdu Next数组