Password

题面翻译

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

不久他们发现了一个字符串 S (1⩽|S|⩽1000000)，刻在和谐寺大门下面的岩石上。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 106 (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;
}

>