传送门

题意：

给出一个字符串，求不等于前后缀的最长的一段子串，使得这段子串即是前缀也是后缀

Solution:

这道题如果使用KMP解决并不这么直观

使用z算法可以轻松地解决（如果没有学过z算法请点击这里）

处理出z数组后，我们记录前i项的z的最大值

对于第i+1项，如果z[i+1]+i==len&&max[i]>=z[i+1],即从i+1开始能匹配到后缀,且前面存在一个相同的串，他所代表的串就是符合条件的

找到最大的即可

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int z[1000010],n,m,r,l;
char b[1000010];
int maxn=0;
int main()
{
    scanf("%s",b);
    m=strlen(b);
    for (int i=1;i<=m;i++)
    {
        if (i>r)
        {
            int t=i,bg=0;
            while (b[t]==b[bg])
                t++,bg++;
            z[i]=bg;
            r=t-1;
            l=i;
        }
        else
        {
            if (z[i-l]<r-i+1) z[i]=z[i-l];
            else
            {
                int t=r+1,bg=r-i+1;
                while (b[t]==b[bg])
                    t++,bg++;
                z[i]=bg;
                r=t-1;
                l=i;
            }
        }
    }
    int nw=0;
    for (int i=1;i<m;i++)
    {
        if (i+z[i]==m&&nw>=z[i])
            maxn=max(maxn,z[i]);
        nw=max(nw,z[i]);
    }
    if (maxn==0) printf("Just a legend");
    for (int i=0;i<maxn;i++)
        printf("%c",b[i]);
}