【HDU 1358】Period（KMP求字符串周期）

骑猪看日落 2022-02-14 02:09 250阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1358][http_acm.hdu.edu.cn_showproblem.php_pid_1358]

### 题意： ###

对于一个字符串的所有前缀中，如果某个前缀的周期大于1就输出此前缀的长度和它循环节的个数。

### 思路： ###

求出每个字符串的next数组，还要知道 i - nxt \[ i \]是每个前缀的循环节长度，然后判断前缀的长度是否是循环节的倍数就可以了。

### My Code： ###

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<queue>
    #include<math.h>
    #include<set>
    using namespace std;
    #define INF 1e9
    typedef long long ll;
    char ch[1000005];
    int nxt[1000005],len1;
    void GetNext()///求next数组 
    {
        int j = 0,k = -1;
        nxt[0] = -1;
        while(j < len1)
        {
            if(k == -1 || ch[j] == ch[k])
            {
                j++;k++;
                nxt[j] = k;
            }
            else k = nxt[k];
        }
    }
    int main()
    {
    	int t = 0;
        while(~scanf("%d",&len1) && len1)
        {
        	getchar();
        	memset(ch,'\0',sizeof(ch));
        	scanf("%s",ch);
        	printf("Test case #%d\n",++t);
        	GetNext();
        	for(int i = 2; i <= len1; i++)
        	{
        		int ans = i-nxt[i];///计算出循环节的长度 
        		if(i/ans > 1 && i%ans == 0)///周期要大于1并且前缀的长度必须是循环节长度的倍数 
        			printf("%d %d\n",i,i/ans);
    		}
    		printf("\n");
    	}
    
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1358]: http://acm.hdu.edu.cn/showproblem.php?pid=1358

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1358(kmp)

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

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

相关 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 赞/ 174 阅读

相关 Hdu 1713 相遇周期

题目：相遇周期 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

系统管理员/ 2022年06月10日 12:23/ 0 赞/ 133 阅读

相关【kmp算法next数组-串的最小循环节/循环周期】Period HDU - 1358

Think: 1知识点：通过kmp算法的next数组求解串的最小循环节和循环周期 2题意：一个长为N (2 <= N <= 1 000 000) 的字符串，询问前缀串长

迈不过友情╰/ 2022年06月07日 02:22/ 0 赞/ 183 阅读

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

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

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

相关 HDU - 1358 Period (KMP)

Period Problem Description For each

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

相关 KMP-(HDU1358)Period[前缀中的周期]

KMP-(HDU1358)Period -------------------- 题目链接：[9:前缀中的周期][9] KMP基础：给个传

矫情吗；*/ 2022年05月17日 01:50/ 0 赞/ 167 阅读

相关 kmp2-HDU1358 HUST1010 POJ2406 POJ2752

HDU1358 [http://acm.hdu.edu.cn/showproblem.php?pid=1358][http_acm.hdu.edu.cn_showprob

Dear 丶/ 2022年05月14日 11:25/ 0 赞/ 152 阅读

相关【HDU 1358】Period（KMP求字符串周期）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1358][http_acm.hdu.edu.cn_showproblem.ph

骑猪看日落/ 2022年02月14日 02:09/ 0 赞/ 251 阅读

相关 hdu-1358 Period

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

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