链接:
http://www.codeforces.com/problemset/problem/126/B
题目大意:
给定一个字符串S, 找到一个子串t,使得这个子串既和S的前缀相同,又和S的后缀相同,但是t不能是S的前缀或后缀。
分析与总结:
利用和理解next数组的好题,首先可以找到所有与前缀相同的后缀的长度, 另len=|S|, 那么next[len] 就是最长的与前缀相同的后缀。
然后利用next数组,可以求出所有长度的后缀与前缀相同的长度,用一个vis数组标记。
之后只需要遍历一遍next数组(非开头与结尾),找到最长的长度即可。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1000005;
char S[MAXN];
int f[MAXN];
bool vis[MAXN];
void getNext(char* p,int* f){
int m=strlen(p);
f[0]=f[1]=0;
for(int i=1; i<m; ++i){
int j=f[i];
while(j && p[i]!=p[j]) j=f[j];
f[i+1] = p[i]==p[j]?1+j:0;
}
}
int main(){
while(scanf("%s",S)!=EOF){
getNext(S,f);
int len=strlen(S);
int maxx=f[len];
if(maxx==0){
puts("Just a legend");
continue;
}
memset(vis, 0, sizeof(vis));
vis[maxx]=true;
int j=maxx;
while(j){
vis[f[j]]=true; // 把所有同时是前缀和后缀的长度标记
j=f[j];
}
bool ok=false;
int ans=0,pos=0;
for(int i=2; i<len; ++i){
if(vis[f[i]] && f[i]>ans){
ok=true;
ans=f[i];
}
}
if(!ok){
puts("Just a legend");
}
else{
puts(S+len-ans);
}
}
return 0;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
关于KMP算法中next数组的计算方法研究
在复习数据结构课程的过程中 对kmp算法及next数组的求解过程进行了深度探索 内含具体代码 及求解next数组的详解 望对大家有所帮助
这是基于严蔚敏数据结构中有关KMP算法的NEXT数组的计算过程,与书中的例子基本一致,是学习数据结构字符串KMP算法的一个很要的理解内容。
汇编语言实现kmp(next数组升级)
关于字符串匹配里,KMP算法中next实现实现原理。关于字符串匹配里,KMP算法中next实现实现原理。
KMP算法求next数组这篇博客中有几张图片,但是博客中图片是竖着的,不方便查看,但我又不知道如何旋转图片,提供博客中的图片,方便下载到自己的电脑上进行查看
KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度 也就是说,KMP算法是...
KMP算法中next数组求法.docx
kmp算法中得next数组也叫fail数组的计算很难理解且代码也不容易实现,本代码就是计算fail数组的源代码
算法总结kmp、树状数组、线段树、字典树
KMP算法中求NEXT的方法,希望对大家有所帮助啊,呵呵!!!
KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度 也就是说,KMP算法是...
C++实现kmp字符串匹配算法,算法思想: *KMP算法的思想就是在匹配过程称若发生不匹配的情况 ...*对于next[]数组的定义如下 *next[j]=-1 j=0 *next[j]=max k : 0[0...k-1]=src[j-k,j-1] *next[j]=0 其他
KMP算法的代码优化过程 使用Z-BOX算法计算KMP的next数组方法
严蔚敏的数据结构中关于KMP算法中Next值求解的C代码
实例模拟KMP算法的next失配函数
今天遇到一个KMP算法的题,以前根本没见过,上网查了好多关于KMP,但是讲的都不是很清楚,看的一头雾水,然后就自己研究做出了一个小程序...希望这个小程序可以帮助大家很好的了解KMP算法Next及NextVal序列的求解算法!
要搞懂kmp算法,首先要了解next数组 那么,next数组到底是求什么的呢? 举个例子,有一个字符串abcabdabc, 要求它的最长的相同前缀后缀。 所谓前缀,就是包含了首字母的字符串字串; 所谓后缀,就是包含了末尾字母的...
前缀周期代码,解决POJ上的问题,KMP的NEXT数组应用