`
Coco_young
  • 浏览: 125327 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

[KMP-循环节问题]HDU 1358 period

 
阅读更多

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1358

题目大意:给定一个字符串,求出所有循环的前缀串,输出前缀串的长度和循环的次数(大于一才算循环串)

思路:同上一道题一样,也是求循环节,这里,枚举长度为2-N的所有前缀串(next数组可以一次预处理求出),求出其最小循环节,判断前缀串长度是否可以整除循环节长度整除,并且前缀串长度不等于循环节长度,满足条件就输出。

代码:

#include<iostream>
using namespace std;
const int MAXN = 1111111;
int N,next[MAXN],cas;
char s[MAXN];
void makenext(){
    int i = 0,j = -1;
    next[0] = -1;
    while(i<=N){
        if(s[i]==s[j]||j==-1)next[++i]=++j;
        else j = next[j];
    }
}
void solve(){
    for(int i=2;i<=N;i++){
        int L = i-next[i];
        if((i%L)==0&&(i/L)!=1){
            printf("%d %d\n",i,i/L);
        }
    }
}
int main(){
    while(scanf("%d",&N),N){
        scanf("%s",s);
        makenext();
        printf("Test case #%d\n",++cas);
        solve();
        puts("");
    }
    return 0;
}


分享到:
评论

相关推荐

    veeamsnap-kmp-default-3.0.2.1185_3.0.101_63-2.1.x86_64.rpm

    veeam agent for linux (veeamsnap-kmp-default-3.0.2.1185_3.0.101_63-2.1.x86_64)

    论文研究 - 树突状细胞的新的疫苗策略提出动素样膜(KMP-11)作为免疫原,以控制实验性内脏利什曼病

    现有报告表明,利什曼原虫多诺万尼抗原KMP-11在调节内脏利什曼病(VL)中的免疫应答中可能很重要。 这项研究评估了在感染的BALB / c小鼠中通过鼠类树突细胞针对VL呈递KMP-11抗原的疫苗前景。 我们在这里报告说,通过...

    broadcom-wl-kmp-default-6.30.223.271_k5.7.11_1-12.37.x86_64.rpm

    飞行堡垒FX50J无线网卡驱动,安装linux时无法打开wifi时安装使用,已在archlinux 安装中实际使用

    模式匹配,KMP算法,string-match-kmp-master.zip

    本项目"string-match-kmp-master.zip"显然专注于介绍和实现KMP算法。 KMP算法的主要目标是在一个大的文本串(text)中查找是否存在一个给定的小的模式串(pattern)。相比于朴素的字符串匹配方法,KMP算法通过构建...

    kmp算法,kmp-algorithm-master (1).zip

    在"KMP-algorithm-master"项目中,可能包含了KMP算法的实现代码,这为学习和理解KMP算法提供了直观的实例。通过阅读和理解这些代码,开发者可以更好地掌握KMP算法的工作原理,并将其应用于实际问题中。此外,该项目...

    elx-lpfc-kmp-default-11.4.334.26_3.0.101_63-1.sles11sp4.x86_64

    elx-lpfc-kmp-default-11.4.334.26_3.0.101_63-1.sles11sp4.x86_64 安装包,希望能帮助到大家。

    kmp算法kmp-algorithm-master.zip

    《深入理解KMP算法》 KMP算法,全称为Knuth-Morris-Pratt算法,是字符串匹配领域中的一种高效算法,由Don Knuth、...理解和掌握KMP算法,对于提升程序设计能力,尤其是在处理字符串相关问题时,具有重要的实践意义。

    KMP-----c语言代码实现,能够实现查找功能

    C语言实现 WIN-TC专用 实现高速关键字查找功能

    KMP-suanfa.rar_kmp string

    在处理大量数据的文本搜索、文本处理以及计算机科学中的许多其他问题时,KMP算法显示出了其优越性。 ### 1. 算法思想 KMP算法的核心在于构建一个“部分匹配表”(也称“失配表”或“前缀后缀表”),用于指导匹配...

    D-KMP-sample.zip

    也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'和pattern='ababc',子串是包含在主串中的,同时它...

    KMP--suanfa.rar_KMP_KMPsuanfa_kmp java_kmp suanfa_vague

    初看kmp算法的时候有点模糊,第一次就根本没明白过。 仔细的推敲。找相关类似的问题。现在把源程序贴出来供大家参考。 关键一点就是要了解next函数的构造,以及为什么要这么做。在数据结构中的next推倒,不过不是很...

    数据结构KMP-NEXT数组计算方法

    ### 数据结构KMP-NEXT数组计算方法 #### KMP算法简介 KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和Vaughan Pratt共同提出。相较于朴素的字符串匹配算法,KMP算法...

    KMP-fail.rar_kmp fail_kmp的fail_kmp算法fail数组_kmp算法求fail

    《深入理解KMP算法及其fail数组的计算》 KMP(Knuth-Morris-Pratt)算法是一种在字符串中寻找子串的搜索算法,由Donald Knuth、James H. Morris和 Vaughan Pratt共同提出。该算法避免了在模式匹配过程中不必要的...

    KMP-string-matching-algorithm.rar_BBC算法_KMP algorithm

    字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”...许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。

    KMP - v1.0.pdf

    该算法解决了在文本串中查找模式串出现位置的问题,并且大大提高了匹配的效率,尤其是在遇到模式串和文本串的字符不匹配时,能够使算法不必回溯到模式串开始位置。 KMP算法的核心在于利用已经部分匹配的有效信息,...

    kmp.rar_KMP

    总的来说,KMP算法是字符串匹配问题的一个重要解决方案,通过预处理部分匹配表,能够有效地处理字符串的匹配问题,提高算法的执行效率。对于学习数据结构和算法的人来说,理解和掌握KMP算法是提升算法能力的重要一步...

    DS串应用--KMP算法

    DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法

    HDU-2000-2099.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个知名的编程竞赛平台,为编程爱好者提供了大量的算法题目进行练习和比赛。这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些...

    KMP-Expander:适用于CSV文件的Mario Kart 7的KMP编辑器

    3. **错误检查与修复**:KMP-Expander会检测并报告潜在的数据问题,帮助确保生成的KMP文件符合游戏的规范,避免因数据错误导致的游戏崩溃或异常。 4. **兼容性提示**:对于不兼容或不常见的数据,工具会给出警告,...

    kmp算法--VC6.0

    在VC6.0环境下实现KMP算法,你需要理解C++的基本语法和数据结构,如字符串操作、数组以及循环结构。代码中可能会包括构造前缀表的函数、进行字符串匹配的函数,以及主程序来调用这些函数并处理输入输出。 总结来说...

Global site tag (gtag.js) - Google Analytics