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

[KMP-求循环节]HDU 3746 Cyclic Nacklace

 
阅读更多

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

题目大意:给定一个字符串,求出最少在末尾添加几个字符使得字符串成为循环串。

解题思路:先求出最小循环节,如果最小循环节长度等于字符串长度,则添加的字符数为字符串的长度,否则用字符串的长度模循环节的长度,如果为0,说明已经是循环串,如果非0,说明还要添加字符串长度减去该值个字符.

代码:

#include<iostream>
using namespace std;
const int MAXN = 111111;
int T,next[MAXN];
char s[MAXN],t[MAXN];
void makenext(char *s){
    int N = strlen(s);
    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];
    }
}

int solve(){
    int N = strlen(s);
    int L = N-next[N];
    if(N==L)return N;
    if(N%L)return L-N%L;
    else return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        makenext(s);
        printf("%d\n",solve());
    }
    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算法的工作原理,并将其应用于实际问题中。此外,该项目...

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

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

    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、Vernon Morris和James H. Pratt三位学者在1970年代提出。这个算法主要用于在一个主串(文本串)中...

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

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

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

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

    KMP-suanfa.rar_kmp string

    **KMP算法详解** KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由D.E. Knuth、V.R. Morris和J.H. Pratt三位学者于1970年代提出。该算法避免了在匹配过程中不必要的字符比较,从而显著提高了字符串...

    KMP--suanfa.rar_KMP_KMPsuanfa_kmp java_kmp suanfa_vague

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

    D-KMP-sample.zip

    kmp算法 KMP算法是什么? 引用自百度百科: KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配...

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

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

    KMP - v1.0.pdf

    KMP算法是一种高效的字符串匹配算法,由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出,因而得名KMP。该算法解决了在文本串中查找模式串出现位置的问题,并且大大提高了匹配的效率,尤其是在遇到模式串和文本串的字符不...

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

    《KMP-Expander:CSV格式的Mario Kart 7赛道编辑工具详解》 在电子游戏领域,特别是赛车游戏,Mario Kart 7凭借其丰富的赛道设计和竞技性深受玩家喜爱。为了满足玩家对自定义赛道的需求,开发人员和爱好者们创造了...

    kmp.rar_KMP

    在"kmp.cpp"源代码中,可能包含了KMP算法的C++实现,包括部分匹配表的生成和主循环匹配过程。而"www.pudn.com.txt"可能是用于测试KMP算法的输入文本,可能包含了一些字符串,用于查找特定的子串。 KMP算法的时间...

    DS串应用--KMP算法

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

    kmp算法--VC6.0

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

    KM匹配题集

    - **【HDU 2282】Chocolate KM**、**【HDU 2813】One fight one KM**、**【HDU 1853】Cyclic Tour**:这些题目可能与KMP算法有关,但具体问题需要看题目详情来解答。 - **【HDU 3488】Tour 最小费用圈覆盖**、**...

Global site tag (gtag.js) - Google Analytics