大致题意:
给出一个字符串str,求出str中存在多少子串,使得这些子串既是str的前缀,又是str的后缀。从小到大依次输出这些子串的长度。
大致思路:
如左图,假设黑色线来代表字符串str,其长度是len,红色线的长度代表next[len],根据next数组定义易得前缀的next[len]长度的子串和后缀next[len]长度的子串完全相同(也就是两条线所对应的位置)。我们再求出next[len]位置处的next值,也就是图中蓝线对应的长度。同样可以得到两个蓝线对应的子串肯定完全相同,又由于第二段蓝线属于左侧红线的后缀,所以又能得到它肯定也是整个字符串的后缀。
所以对于这道题,求出len处的next值,并递归的向下求出所有的next值,得到的就是答案。
#include<iostream>
#include<cstring>
#include<stack>
#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;
}
}
stack<int>ans;
int main(){
while(scanf("%s",pat)!=EOF){
lenp=strlen(pat);
get_next();
int j=next[lenp-1];
while(j!=-1){
ans.push(j);
j=next[j];
}
while(!ans.empty()){
cout<<ans.top()+1<<" ";
ans.pop();
}cout<<lenp<<endl;
}
return 0;
}
分享到:
相关推荐
pku acm 2752 Seek the Name, Seek the Fame代码 kmp算法。解题报告:http://blog.csdn.net/china8848
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算法通过使用一个称为...
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报告:元宇宙产品概念,哪一种消费者更有感 12.15-31页.pdf
kmp算法
KMP扩展器 适用于CSV文件的Mario Kart 7的KMP编辑器。
模板-kmp-库 Kotlin多平台库模板。 有一个针对多平台库的基线设置,该库支持除弃用的wasm32之外的所有kotlin。 特征 本机目标分组和共享sourceSet 包装程序库模块,它声明对所有lib模块的依赖关系 通过allprojects...
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kmp算法:查找一个字符串是不是另一个字符串的子串
KMP算法
The classical KMP algorithm for string matching (the target string can be modified in the main function, if any match is found, the matching position would be returned)
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算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
本代码实现的是程序内容:数据结构中的KMP算法