大致题意:
给出一个长度为n的字符串,分别求出前n位前缀,分别可以由多少个相同的子串连接而成。
大致思路:
依旧是next数组的灵活运用,和poj2406差不多,在此不在赘述。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
int main(){
int cas=0;
while(scanf("%d",&lenp)!=EOF&&lenp){
cas++;
scanf("%s",pat);
printf("Test case #%d\n",cas);
get_next();
for(int i=2;i<=lenp;i++){
int l=(i-1)-next[i-1];
if(i%l==0&&i!=l){
cout<<i<<" "<<i/l<<endl;;
}
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
D-KMP体系结构-官方样本这是D-KMP架构的官方示例,展示了一个适用于Android和iOS的简单主/详细应用程序。 有关D-KMP体系结构的更多信息,请阅读相关的。D-KMP体系结构的主要功能: 它使用最新的声明性UI工具包:适用...
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
pku acm 1961 Period代码 kmp算法。解题报告:http://blog.csdn.net/china8848
KMP报告:元宇宙产品概念,哪一种消费者更有感 12.15-31页.pdf
KMP扩展器 适用于CSV文件的Mario Kart 7的KMP编辑器。
kmp算法
D-KMP架构Daniele Baroncelli建议的D-KMP体系结构的试用示例,位于: ://danielebaroncelli.medium.com/the-future-of-apps-declarative-uis-with-kotlin-multiplatform-d-kmp-part-1 它:声明性UI(Jetpack编写)...
模板-kmp-库 Kotlin多平台库模板。 有一个针对多平台库的基线设置,该库支持除弃用的wasm32之外的所有kotlin。 特征 本机目标分组和共享sourceSet 包装程序库模块,它声明对所有lib模块的依赖关系 通过allprojects...
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kmp算法:查找一个字符串是不是另一个字符串的子串
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
使用KMP算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
kmp(kangle+mysql+php)集成版,支持asp、asp.net、php脚本环境,集成mysql数据库和phpmyadmin管理工具。kmp包含组件:kangle 2.1.8mysql-5.5.8php-5.2.17ZendOptimizer-3.3.9phpmyadmin-3.3.9