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

﹏ヽ暗。殇╰゛Y 2022-05-19 07:11 179阅读 0赞

[传送门][Link 1]

题意：给你两个字符串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;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2594

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关 [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher J - Simpsons’ Hidden Talents HDU - 2594(kmp前后缀）...

J - Simpsons’ Hidden Talents HDU - 2594 题目链接：[https://vjudge.net/contest/70325\probl

男娘i/ 2023年08月17日 15:41/ 0 赞/ 116 阅读

相关 hdu2594Simpsons’ Hidden Talents（kmp）

Simpsons’ Hidden Talents Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 3276

女爷i/ 2022年08月21日 10:47/ 0 赞/ 44 阅读

相关 HDU 2594 Simpsons’ Hidden Talents（KMP）

Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware

我就是我/ 2022年06月10日 14:21/ 0 赞/ 137 阅读

相关【kmp算法next数组应用】Simpsons’ Hidden Talents HDU - 2594

Think: 1知识点：kmp算法next数组应用 2题意：输入两个串，询问“最长前后缀”，“最长前后缀”定义为：串ans为st1的前缀，st2的后缀，输出“最长前后缀

Dear 丶/ 2022年06月07日 02:41/ 0 赞/ 219 阅读

相关 HDU - 2594 Simpsons’ Hidden Talents (KMP)

Simpsons’ Hidden Talents Problem Description Homer: Ma

深藏阁楼爱情的钟/ 2022年05月19日 08:40/ 0 赞/ 166 阅读

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

[传送门][Link 1] 题意：给你两个字符串s1和s2，它们的长度不超过50000，问你s1的前缀和s2的后缀所能匹配的最大长度，如果无法匹配就输出0，否则就输出这个最大

﹏ヽ暗。殇╰゛Y/ 2022年05月19日 07:11/ 0 赞/ 180 阅读

相关 Hdu 3746 Cyclic Nacklace(KMP Next数组的应用)

[传送门][Link 1] 题意：给你一个字符串，问你最少还需要补多少个字符使得字符串构成循环。分析：这道题其实是考对Next数组的理解，Next数组其实可以看成是一个保

约定不等于承诺〃/ 2022年05月19日 07:04/ 0 赞/ 190 阅读

相关 R - Simpsons’ Hidden Talents

题目描述： Homer: Marge, I just figured out a way to discover some of the talents we weren

爱被打了一巴掌/ 2022年03月21日 13:22/ 0 赞/ 184 阅读

相关 kuangbin专题十六 KMP&&扩展KMP HDU2594 Simpsons’ Hidden Talents

Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware

我会带着你远行/ 2021年12月24日 03:43/ 0 赞/ 230 阅读

相关数组的应用例子

1、与使用System.arraycopy进行数组复制类似的， Arrays提供了一个copyOfRange方法进行数组复制。不同的是System.

缺乏、安全感/ 2021年12月15日 08:31/ 0 赞/ 292 阅读