传送门:http://poj.org/problem?id=2752
题目描述:要求求出字符串S所有满足如下条件的子串长度(1.子串T为S的前缀 2.子串T为S的后缀)。
解题思路:利用KMP的NEXT数组的特性,Next[pos]的含义是在pos处失配时pos应该指向的下一个位置,那么0-(Next[pos]-1)构成的字符串和(pos-Next[pos])-(pos-1)构成的字符串是相同么,那么即0-(Next[pos]-1)构成的字符串是,0-pos-1构成的字符串的前缀后缀子串,这样,考虑在主串S后面增加一个字符,构成新字符串P,那么求出P最后一个位置的Next[]值,那么就可以按照上述分析来求出前缀后缀子串(PS:要把pos不停的滑动,直到pos=0,因为空串不算是前缀后缀子串)
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 4111111;
char P[MAXN];
int Next[MAXN],M;
vector<int> ans;
void MakeNext(int M){
int i = 0, j = -1;
Next[0] = -1;
while(i<M){
if(j==-1||P[i]==P[j])Next[++i]=++j;
else j = Next[j];
}
}
int main(){
while(scanf("%s",P)!=EOF){
M = strlen(P);
P[M] = '5';P[++M]=0;
ans.clear();
MakeNext(M);
int pos = M-1;
while(pos){
ans.push_back(pos);
pos = Next[pos];
}
for(int i=(int)ans.size()-1;i>=0;i--){
if(i)printf("%d ",ans[i]);
else printf("%d\n",ans[i]);
}
}
return 0;
}
分享到:
相关推荐
这是基于严蔚敏数据结构中有关KMP算法的NEXT数组的计算过程,与书中的例子基本一致,是学习数据结构字符串KMP算法的一个很要的理解内容。
pku acm 2752 Seek the Name, Seek the Fame代码 kmp算法。解题报告:http://blog.csdn.net/china8848
关于KMP算法中next数组的计算方法研究
在复习数据结构课程的过程中 对kmp算法及next数组的求解过程进行了深度探索 内含具体代码 及求解next数组的详解 望对大家有所帮助
汇编语言实现kmp(next数组升级)
关于字符串匹配里,KMP算法中next实现实现原理。关于字符串匹配里,KMP算法中next实现实现原理。
KMP算法求next数组这篇博客中有几张图片,但是博客中图片是竖着的,不方便查看,但我又不知道如何旋转图片,提供博客中的图片,方便下载到自己的电脑上进行查看
kmp算法中得next数组也叫fail数组的计算很难理解且代码也不容易实现,本代码就是计算fail数组的源代码
kmp算法 KMP算法是什么? 引用自百度百科: KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配...
KMP算法中next数组求法.docx
现有报告表明,利什曼原虫多诺万尼抗原KMP-11在调节内脏利什曼病(VL)中的免疫应答中可能很重要。 这项研究评估了在感染的BALB / c小鼠中通过鼠类树突细胞针对VL呈递KMP-11抗原的疫苗前景。 我们在这里报告说,通过...
kmp算法kmp-algorithm-master.zip
算法总结kmp、树状数组、线段树、字典树
飞行堡垒FX50J无线网卡驱动,安装linux时无法打开wifi时安装使用,已在archlinux 安装中实际使用
kmp算法,kmp-algorithm-master (1).zip
模式匹配,KMP算法,string-match-kmp-master.zip
KMP算法中求NEXT的方法,希望对大家有所帮助啊,呵呵!!!
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
elx-lpfc-kmp-default-11.4.334.26_3.0.101_63-1.sles11sp4.x86_64 安装包,希望能帮助到大家。