codeforces 126 B password (KMP Next数组的妙用)
程序员文章站
2022-05-02 18:12:58
...
题意是求给定的字符串中相同且最长的前缀、后缀、中间子串,其中三者允许有交集,但是中间子串不能包括开头和结尾。
如:fixprefixsuffix,答案为fix。
由next数组性质可知,若不少于两个位置的next值指向同一个位置(显然不包括0),则说明该位置是字符串中相同的前缀、后缀和中间子串。
那么预处理出next数组后,只需要线性从后往前遍历整个数组,将next值放入set或用bool数组标记一下,若当前的next值已经存在于set,则说明是一个可能的解,维护一个最大的可能的解即为答案。
对于前面的例子,长度为15,next[15]=3,next[9]=3,最大长度是3,所以答案就是fix。
如采用set,时间复杂度O(nlogn),用bool数组就直接O(n)
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1000005;
int Next[N];
void preKMP(char x[],int m,int kmpNext[]){
int i,j;
j=kmpNext[0]=-1;
i=0;
while(i<m){
while(-1!=j && x[i]!=x[j]) j=kmpNext[j];
kmpNext[++i]=++j;
}
}
char a[N],ans[]="Just a legend";
bool vis[N];
int main(){
scanf("%s",a);
int len=strlen(a);
preKMP(a,len,Next);
int tmp=len;
while(Next[tmp]>0){
vis[Next[tmp]]=1;
tmp=Next[tmp];
}
int ans1=0;
for(int i=len-1;i>=1;i--){
if(vis[Next[i]]){
ans1=max(ans1,Next[i]);
}
}
if(!ans1) cout<<ans;
else a[ans1]='\0',cout<<a;
return 0;
}