codeforces 126B password[kmp]

题目大意：给定一个字符串，找出其中一个最长的子串，使得这个子串既是前缀又是后缀又在中间出现

题目分析：我们看到前后缀很自然的可以想到Kmp中的next数组，那么如何处理是否在中间呢？我一开始构建了一个s除去头尾的子串，试图在其中用find函数去查找是否存在这样的串，很显然这样的复杂度是很高的，会T，我们可以发现，我们在求next的数组的时候，就是求最长前缀后多少个，因此，我们只要记录除了最后一个字符意外的前面的最长前缀的情况，也就是除去后缀之后，前缀和中间出现的又构成的一个前后缀，我们只要找到满足这样条件的子串即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
const int inf=0x3f3f3f3f;
const int mod =1e9+7;
int next[maxn];
int _hash[maxn];
void getnext(string s)
{
    int len=s.size();
    int i=0,j=-1;
    next[0]=-1;
    while(i<len)
    {
        if(j==-1||s[i]==s[j])
        {
            next[++i]=++j;
        }
        else j=next[j];
    }
    for(int i=1;i<len;i++)
    {
        _hash[next[i]]++;
    }
}
int main()
{
    string a;
    cin>>a;
    getnext(a);
    int len = a.size();
    int k=next[len];

    while(k)
    {
        if(_hash[k])
        {
            for(int i=0;i<k;i++)
            {
                cout<<a[i];
            }
            return 0;
        }
        k=next[k];
    }
    printf("Just a legend\n");
    return 0;
}