题解 CF126B 【Password】

# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/) ~~你没有发现两个字里的blog都不一样嘛~~ qwq ### 一句话题意 求一个给定串$s$的一个子串$T$. 满足 - $T$是$s$的前缀 - $T$是$s$的后缀 - $T$在$s$中间出现过 ### ~~xjb~~分析 首先明确我们要找的是这种情况.  此时,我们发现,蓝色部分好像是什么东西? $KMP$算法中的$next$! (最长公共前后缀的长度 现在明确了我们的解题方法,$KMP$ 那么现在的问题就是要找图中红色部分. #### 如何去找红色部分? 我们发现,可以将图片看成这样.  这样又成了$KMP$算法中的$next$ 那么现在我们需要知道最长的长度. 显然,中间部分的长度可能比$s$的前缀或后缀长亦可能短,但是长度最大只可能是$next[n]$. 即真实答案$ans \leq next[n]$ 所以我们需要在$2 $到$n-1$中找到第一个比$next[n]$小的位置。 而,我们需要记录一下$mxx=\sum_{i=2}^{n-1}next_i$ 有什么用? > 考虑一下我们的中间部分的子串长度只可能是$\leq next[n]$的,因此我们要一直跳转$next[n]$知道某个位置小于等于中间部分最长子串的长度. 这个时候问题得以解决. 判断无解的话只需要判断跳转到的$next$是否为$0$输出$Just\ a\ legend$即可。 最后只需要枚举$i$从$2$到$n-1$去找那个$next[i]$即可. 然后直接输出即可. ``代码`` ```c++ #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define R register using namespace std; char s[1000080]; int len,nex[1000080],k,mxx,now; inline void judge() { if(!now) { puts("Just a legend"); exit(0); } } int main() { scanf("%s",s+1); len=strlen(s+1);nex[1]=0; for(R int i=2;i<=len;i++) { while(k and s[k+1]!=s[i])k=nex[k]; if(s[i]==s[k+1])k++; nex[i]=k; if(i!=len)mxx=max(nex[i],mxx); } now=nex[len]; judge();while(now>mxx)now=nex[now];judge(); for(R int i=2;i<len;i++) if(now==nex[i]) { for(R int j=i-now+1;j<=i;j++) printf("%c",s[j]); exit(0); } } ```