字符串练习：Password

· · 题解

传送门

  大佬们都打什么 Z 算法，我这个蒟蒻只能用 KMP 来水一发

  我们注意到"前后缀"都是可以直接用 KMP 里的 next 数组求出来的。关键在于一个位于中间的字串 T。

  若在中间的字串 T 结束于 str[i]，那么 T 一定是 str[1..i] 的公共前后缀。看到公共前后缀，自然而然我们可以再次使用 KMP。

  又因为中间的那个字串 T 的结尾只可能在 str[2] ...str[n-1]之间，那么我们最后字串的长度就不会超过 \max(kmp[2..n-1]) 。我们把这个最大值记作 maxn

  那么这个 T 又是整体的公共前后缀，那么我们从 kmp[n] 开始枚举。如果长度超过 maxn 了，我们就跳转到 kmp[kmp[n]]；以此类推直到为 0，如果为 0 了，直接输出 Just a legend 即可。

  当我们当前的长度 len <= maxn 后，就要看中间是否存在一个 kmp[k] = len 的了。在这里我认为 KMP 的题解里最后遍历 kmp[2..n-1] ，看哪个等于 len，再直接输出的做法是不必要的。我们很容易就可以证明 kmp[2..n-1] 中一定有一个的值是等于 len 的，即一定存在一个位于中间的跟长度为 len 的前（后）缀相同的字串 T。

  原因何在？回想一下我们 kmp 数组的推导过程，除了 kmp[i] = 0 的情况，所有的 kmp[i]，都一定是从一个比它少 1 的 kmp 值 +1得来的。举个例子，若 kmp[1..n] 里有一个值为 3 的，非常显然也有一个长度为 2 的 kmp 值。（你的代码里是不是有一个 "if 相等 ： j++" 的语句？）

  那么我们就得出了一个结论：1~maxn 这些值都存在于 kmp[2..n-1] 中。又知道这个 len 一定满足 1<=len<=maxn，那么，kmp[2..n-1] 一定有一个值为 len。因此我们直接输出 str[1..j] 即可。

  最后贴上AC代码，供各位 dalao 参考

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
char str[MAXN];
int fail[MAXN],n,maxn=0;
int main(){
    cin>>(str+1);
    n=strlen(str+1);
    fail[1]=0;
    int j=0;
    for(int i=2;i<=n;i++){
        while(j&&str[j+1]!=str[i]){
            j=fail[j];
        }
        if(str[j+1]==str[i])j++;
        fail[i]=j;
        if(i!=n){
            maxn=max(maxn,j);
        } 
    }
    j=fail[n];
    if(maxn==0 || j==0){
        printf("Just a legend");
        return 0;
    }
    while(j>maxn){
        j=fail[j];
    }
    if(j==0){
        printf("Just a legend");
        return 0; 
    }
    for(int k=1;k<=j;k++){
        printf("%c",str[k]);
    }
    printf("\n");
    return 0;
}