CF126B

Password

题面翻译

Asterix，Obelix 和他们的临时伙伴 Suffix、Prefix 已经最终找到了和谐寺。然而和谐寺大门紧闭，就连 Obelix 的运气也没好到能打开它。

不久他们发现了一个字符串 \(S\ (1\leqslant\vert S\vert\leqslant1000000)\)，刻在和谐寺大门下面的岩石上。Asterix 猜想那一定是打开寺庙大门的密码，于是就大声将字符串朗读了出来，然而并没有什么事发生。于是 Asterix 又猜想密码一定是字符串 \(S\) 的子串 \(T\)。

Prefix 认为 \(T\) 是 \(S\) 的前缀，Suffix 认为 \(T\) 是 \(S\) 的后缀，Obelix 却认为 \(T\) 应该是 \(S\) 中的某一部分，也就是说，\(T\) 既不是 \(S\) 的前缀，也不是 \(S\) 的后缀。

Asterix 选择子串 \(T\) 来满足所有伙伴们的想法。同时，在所有可以被接受的子串变形中，Asterix 选择了最长的一个。当 Asterix 大声读出子串 \(T\) 时，寺庙的大门开了。（也就是说，你需要找到既是 \(S\) 的前缀又是 \(S\) 的后缀同时又在 \(S\) 中间出现过的最长子串）

现在给你字符串 \(S\)，你需要找到满足上述要求的子串 \(T\)。

输入格式

一行一个只包含小写字母的字符串 \(S\)。

输出格式

输出子串 \(T\)，如果 \(T\) 不存在，输出 Just a legend。

题目描述

Asterix, Obelix and their temporary buddies Suffix and Prefix has finally found the Harmony temple. However, its doors were firmly locked and even Obelix had no luck opening them.

A little later they found a string $ s $ , carved on a rock below the temple's gates. Asterix supposed that that's the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring $ t $ of the string $ s $ .

Prefix supposed that the substring $ t $ is the beginning of the string $ s $ ; Suffix supposed that the substring $ t $ should be the end of the string $ s $ ; and Obelix supposed that $ t $ should be located somewhere inside the string $ s $ , that is, $ t $ is neither its beginning, nor its end.

Asterix chose the substring $ t $ so as to please all his companions. Besides, from all acceptable variants Asterix chose the longest one (as Asterix loves long strings). When Asterix read the substring $ t $ aloud, the temple doors opened.

You know the string $ s $ . Find the substring $ t $ or determine that such substring does not exist and all that's been written above is just a nice legend.

输入格式

You are given the string $ s $ whose length can vary from $ 1 $ to $ 10^{6} $ (inclusive), consisting of small Latin letters.

输出格式

Print the string $ t $ . If a suitable $ t $ string does not exist, then print "Just a legend" without the quotes.

样例 #1

样例输入 #1

fixprefixsuffix

样例输出 #1

fix

样例 #2

样例输入 #2

abcdabc

样例输出 #2

Just a legend

看到这题的第一眼，想到的肯定是KMP（因为需要求最长公共前后缀嘛，将其记作\(t\)，母串记作\(s\)）。 但是，\(t\)还需要是\(s\)的中间部分，这个怎么办？？？ 我们可以将它转化为熟悉的问题，画个图解释一下： 这样就一目了然了吧，\(t\)也是中间的橙色串的最长前后缀，这就转化成了我们熟悉的问题。

那么我们只要\(2\)遍历到\(n-2\)，只要\(pmt[i]==pmt[n-1]\)，那么我们就找到最长的\(t\)了。

但是，实际上可能是找不到的（看题意就知道了），如果\(pmt[n-1]\)比\(max(pmt[i])\)还大，所以这时\(t\)的长度就得缩小了（也就是不断地往回跳：\(pmt[pmt[n-1]]\)，\(pmt[pmt[pmt[n-1]]]······\)，直到小于\(max(pmt[i])\)，注意\(i<=n-2\)）。

可能有点混乱，将上述的步骤总结一下： 1、先预处理出\(max(pmt[i])，i<=n-2\)。 2、判断\(pmt[n-1]\)与\(max(pmt[i])\)的大小关系，如果\(pmt[n-1]>=max(pmt[i])\)，就得往回跳，直到小于\(max(pmt[i])\)为止（记作\(len\)吧)，当然有可能跳到0，那么这时候就无解了。 3、如果有解，那么我们只需要输出\(0\)~\(len-1\)即可，毕竟\(len\)是字符串的长度。

我们可以在第二步开始前加上特判\(pmt[n-1]==0\)是否成立，如果成立，就说明前后缀不同，肯定无解。

AC代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
int pmt[MAXN],maxn;
void get_pmt(const string &s){
    for(int i=1,j=0;i<s.length();i++){
        while(j&&s[i]!=s[j])j=pmt[j-1];
        if(s[i]==s[j])j++;
        pmt[i]=j;
        if(i!=s.length()-1){
            maxn=max(maxn,pmt[i]);
        }
    }
}
int main(){
    string s;
    cin>>s;
    get_pmt(s);
    int n=s.length();
    int len=pmt[n-1];
    if(len==0){
        cout<<"Just a legend\n";
    }
    else{
        while(len>maxn){
            len=pmt[len-1];
        }
        if(len==0){
            cout<<"Just a legend\n";
        }
        else{
            for(int i=0;i<len;i++){
                cout<<s[i];
            }
        }
    }
    return 0;
}

>