HDU 1358(kmp)

叁歲伎倆 2022-09-20 12:44 2阅读 0赞

题意：给出一个数字n，接下来一行是一个字符串，n是这个字符串的长度。求这个字符串的所有是循环字符串的前缀。

kmp中的next数组只得是第i个字符匹配错误，向前跳的位置next【i】。

#include<algorithm>
    #include<stdio.h>
    #include<string>
    #include<string.h>
    #include<math.h>
    #include<queue>
    #include<iostream>
    using namespace std;
    
    int i,j,k;
    
    int len;
    
    char s[1000001];
    
    int next[1000001];
    
    void get_next()  
    {  
        int i=0,j=-1;  
        next[0]=-1;  
        for(;s[i];)  
            if(j==-1||s[i]==s[j])  
            {  
                ++i;++j;  
                next[i]=j;  
            }  
            else j=next[j];  
    }  
     
    
    int main(){
    
    int t=1;
    
        while(scanf("%d",&len)&&len){
    
            getchar();
    
            scanf("%s",s);
    
            get_next();
    
            printf("Test case #%d\n",t++);
    
            for(i=2;i<=len;i++){
    
                 j=i-next[i];
    
                 if(i%j==0){
    
                     if(i/j>1) printf("%d %d\n",i,i/j);
    
                }
    
            }
    
            printf("\n");
    
        }
    
        return 0;
    
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 [kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher E - Period HDU - 1358(循环节kmp)

E - Period HDU - 1358 题目链接：[https://vjudge.net/contest/70325\problem/E][https_vjudge.

小灰灰/ 2023年08月17日 15:40/ 0 赞/ 113 阅读

相关 HDU 1358(kmp)

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

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

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

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

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

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

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

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

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

相关 HDU - 1358 Period (KMP)

Period Problem Description For each

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

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

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

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

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

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

相关 hdu-1358 Period

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

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