首页 > 代码库 > codeforces 126B

codeforces 126B

2024-08-31 23:01:24   217人阅读

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.

Input

You are given the string s whose length can vary from 1 to 106 (inclusive), consisting of small Latin letters.

Output

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

Example
Input
fixprefixsuffix
Output
fix
Input
abcdabc
Output
Just a legend
完全没有想法。先开始脑抽了，想了个二分，很激动的认为对了，结果wa，然后发现公共前缀的公共后缀的长度似乎不能二分。。。gg
又学了一下kmp。。。之前学的忘光了。。。
还是不太懂（mark）
这道题巧妙地利用了kmp中的nxt，这里的nxt就是kmp中预处理的失配函数。nxt[i]表示的是[1-i]位置的字符串中最长的前缀和后缀的公共部分的长度(s=abcab的nxt[5]=2,因为s[1-2]=s[4-5])
我们要求的正好和nxt所表示的东西很相似，于是就用上。
求完nxt，把每个长度标记。nxt[n]不标记，因为这是开头和结尾，不能算作中间的最长长度
从nxt[n](n是字符串长度)开始,表示的是整个串的前后缀最长公共部分的长度，如果这个长度存在，那么就可以了。（因为这个是最大的nxt,nxt是递减的）
挖个坑，似乎还是不是很理解
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000010
int n;
int nxt[N],used[N];
char s[N];
void Init()
{
    int j=0;
    for(int i=2;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1]) j=nxt[j];
        if(s[i]==s[j+1]) j++;
        nxt[i]=j;
    }
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    Init();
    for(int i=1;i<n;i++) used[nxt[i]]=1;
    used[0]=0;
    for(int i=n;i;i=nxt[i]) if(used[nxt[i]])
    {
        for(int j=1;j<=nxt[i];j++) printf("%c",s[j]);
        return 0;
    }
    printf("Just a legend");
    return 0;
}

 

codeforces 126B


联系
我们