大致题意:
给出一个字符串,求最少再增加多少个字符才能使得这个字符串成为一个重复串。
大致思路:
KMP最小覆盖子串的小小变形,最小覆盖子串的长度为len-(next[len-1])~~具体请参见 http://blog.csdn.net/fjsd155/article/details/6866991 另外poj2185也是这类题
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax= 100005;
const int mMax=1000005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){ //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
int main(){
int t,a,b;
scanf("%d",&t);
while(t--){
scanf("%s",pat);
lenp=strlen(pat);
get_next();
a=next[lenp-1]+1;
a=lenp-a; //最小覆盖子串长度
b=lenp%a;
if(b){
printf("%d\n",a-b);
}
else{
if(a==lenp){
printf("%d\n",lenp);
}
else{
printf("0\n");
}
}
}
return 0;
}
分享到:
相关推荐
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算法通过使用一个称为...
KMP扩展器 适用于CSV文件的Mario Kart 7的KMP编辑器。
KMP报告:元宇宙产品概念,哪一种消费者更有感 12.15-31页.pdf
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
kmp算法 KMP算法是一种用于在一个文本串S中查找一个模式串P出现位置的高效算法。KMP算法的核心思想是利用模式串P本身的信息来避免在文本串S中进行不必要的匹配。具体来说,KMP算法通过预处理模式串P,构建一个部分...
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--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
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
使用KMP算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
扩展的KMP问题: 给定母串S,和子串T。 定义n=|S|, m=|T|,extend[i]=S[i..n]与T的最长公共前缀长度。请在线性的时间复杂度内,求出所有的extend[1..n]。