传送门: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;
}
分享到:
相关推荐
veeam agent for linux (veeamsnap-kmp-default-3.0.2.1185_3.0.101_63-2.1.x86_64)
现有报告表明,利什曼原虫多诺万尼抗原KMP-11在调节内脏利什曼病(VL)中的免疫应答中可能很重要。 这项研究评估了在感染的BALB / c小鼠中通过鼠类树突细胞针对VL呈递KMP-11抗原的疫苗前景。 我们在这里报告说,通过...
飞行堡垒FX50J无线网卡驱动,安装linux时无法打开wifi时安装使用,已在archlinux 安装中实际使用
本项目"string-match-kmp-master.zip"显然专注于介绍和实现KMP算法。 KMP算法的主要目标是在一个大的文本串(text)中查找是否存在一个给定的小的模式串(pattern)。相比于朴素的字符串匹配方法,KMP算法通过构建...
在"KMP-algorithm-master"项目中,可能包含了KMP算法的实现代码,这为学习和理解KMP算法提供了直观的实例。通过阅读和理解这些代码,开发者可以更好地掌握KMP算法的工作原理,并将其应用于实际问题中。此外,该项目...
elx-lpfc-kmp-default-11.4.334.26_3.0.101_63-1.sles11sp4.x86_64 安装包,希望能帮助到大家。
《深入理解KMP算法》 KMP算法,全称为Knuth-Morris-Pratt算法,是字符串匹配领域中的一种高效算法,由Don Knuth、...理解和掌握KMP算法,对于提升程序设计能力,尤其是在处理字符串相关问题时,具有重要的实践意义。
C语言实现 WIN-TC专用 实现高速关键字查找功能
在处理大量数据的文本搜索、文本处理以及计算机科学中的许多其他问题时,KMP算法显示出了其优越性。 ### 1. 算法思想 KMP算法的核心在于构建一个“部分匹配表”(也称“失配表”或“前缀后缀表”),用于指导匹配...
也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'和pattern='ababc',子串是包含在主串中的,同时它...
初看kmp算法的时候有点模糊,第一次就根本没明白过。 仔细的推敲。找相关类似的问题。现在把源程序贴出来供大家参考。 关键一点就是要了解next函数的构造,以及为什么要这么做。在数据结构中的next推倒,不过不是很...
### 数据结构KMP-NEXT数组计算方法 #### KMP算法简介 KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和Vaughan Pratt共同提出。相较于朴素的字符串匹配算法,KMP算法...
《深入理解KMP算法及其fail数组的计算》 KMP(Knuth-Morris-Pratt)算法是一种在字符串中寻找子串的搜索算法,由Donald Knuth、James H. Morris和 Vaughan Pratt共同提出。该算法避免了在模式匹配过程中不必要的...
字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”...许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。
该算法解决了在文本串中查找模式串出现位置的问题,并且大大提高了匹配的效率,尤其是在遇到模式串和文本串的字符不匹配时,能够使算法不必回溯到模式串开始位置。 KMP算法的核心在于利用已经部分匹配的有效信息,...
总的来说,KMP算法是字符串匹配问题的一个重要解决方案,通过预处理部分匹配表,能够有效地处理字符串的匹配问题,提高算法的执行效率。对于学习数据结构和算法的人来说,理解和掌握KMP算法是提升算法能力的重要一步...
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
HDU(杭州电子科技大学在线评测系统)是一个知名的编程竞赛平台,为编程爱好者提供了大量的算法题目进行练习和比赛。这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些...
3. **错误检查与修复**:KMP-Expander会检测并报告潜在的数据问题,帮助确保生成的KMP文件符合游戏的规范,避免因数据错误导致的游戏崩溃或异常。 4. **兼容性提示**:对于不兼容或不常见的数据,工具会给出警告,...
在VC6.0环境下实现KMP算法,你需要理解C++的基本语法和数据结构,如字符串操作、数组以及循环结构。代码中可能会包括构造前缀表的函数、进行字符串匹配的函数,以及主程序来调用这些函数并处理输入输出。 总结来说...