Hdu 1358 Period(KMP Next数组的理解)

喜欢ヅ旅行 2022-05-19 07:06 206阅读 0赞

[传送门][Link 1]

题意：给你一个长度为n的（2 <= N <= 1 000 000）字符串，求字符串的所有前缀字符串中字能刚好由k（k>1）个循环节构成的字符串，输出这些k。

分析：由于题目要求k最大，那么其实就是求最小循环节，由于N很大很明显我们不能用暴力解决，我们想到Next数组其实是存了每个子串的前后缀匹配信息的，以i结尾的字符串它的最小循环节minPeriod的长度其实就是 i-Next\[i\] ，所以我们只需要i从小到大扫一遍如果当前 i 能够整除最小循环节，就说明这个子串能够由最小循环节通过循环组成，那么就输出最小循环节循环的次数。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6+5;
    char t[maxn];
    int Next[maxn];
    int N;
    
    void getNext()
    {
        int j = -1,i = 0;
        Next[0] = -1;
        while(i<N)
        {
            if(j==-1||t[i]==t[j])
            {
                ++i;
                ++j;
                Next[i]=j;
            }
            else j = Next[j];
        }
    }
    
    int main()
    {
        int kase = 0;
        while(scanf("%d",&N)&&N)
        {
            scanf("%s",t);
            getNext();
            printf("Test case #%d\n",++kase);
            for(int i=2;i<=N;i++)
            {
                int minPeriod=i-Next[i];
                if(i%minPeriod==0&&i/minPeriod!=1)/**题目要求中 K>1*/
                {
                    printf("%d %d\n",i,i/minPeriod);
                }
            }
            printf("\n");
        }
        return 0;
    }

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

发表评论取消回复

表情：

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

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

相关阅读

相关 KMP中next数组的理解与应用

理解 1、next数组一直往前走 next数组一直往前走，得到的所有前缀也是当前主串的后缀，当然了，也是当前主串的前缀。![1365470-201901311224

迷南。/ 2023年08月17日 15:47/ 0 赞/ 124 阅读

相关 HDU 1358(kmp)

题意：给出一个数字n，接下来一行是一个字符串，n是这个字符串的长度。求这个字符串的所有是循环字符串的前缀。 kmp中的next数组只得是第i个字符匹配错误，向前跳的位置nex

叁歲伎倆/ 2022年09月20日 12:44/ 0 赞/ 20 阅读

相关 HDU 1358 Period（KMP+next数组的运用）

For each prefix of a given string S with N characters (each character has an ASCII code

刺骨的言语ヽ痛彻心扉/ 2022年06月10日 13:52/ 0 赞/ 173 阅读

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

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

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

相关 Hdu 1358 Period(KMP Next数组的理解)

[传送门][Link 1] 题意：给你一个长度为n的（2 <= N <= 1 000 000）字符串，求字符串的所有前缀字符串中字能刚好由k（k>1）个循环节构成的字符串，输

喜欢ヅ旅行/ 2022年05月19日 07:06/ 0 赞/ 207 阅读

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

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

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

相关 HDU - 1358 Period (KMP)

Period Problem Description For each

灰太狼/ 2022年05月18日 20:45/ 0 赞/ 188 阅读

相关 HDU 2874 Connections between cities——————KMP next数组的利用

Period Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

我就是我/ 2022年05月16日 09:08/ 0 赞/ 169 阅读

相关 HDU 3746 Cyclic Nacklace——————KMP_next[]数组的利用

Cyclic Nacklace Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (J

桃扇骨/ 2022年05月16日 09:05/ 0 赞/ 160 阅读

相关 hdu-1358 Period

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1358 题目类型：字符串-KMP 题意概括：找出从第二个字符开始

谁践踏了优雅/ 2021年09月29日 22:20/ 0 赞/ 198 阅读