kmp

题意：

图片说明

分析：

我们看着一题，我们仔细想想。首先如果没有要求中间 子串 的话，就很简单了。我们直接输出前后缀相等的就好了。
无论是 kmp 还是 暴力 都是线性时间。

但是麻烦就在于中间要有字串。

那我们想想，如何判断中间有没有子串呢？

假设，next[n] = k 意味着s0,s1,s2,s3,s4.....sk-1 == sn-k+1,sn-k+2.....sn
子串即为s[0:k] 那么如何判断中间有没有子串呢？
如果有子串，s[i:i+k]那么我肯定s[0:i+k]的next就会是k
想想是不是这样？
也就是说我们求next数组就可以了。
求出next[n]看next[n]的值一共被取了几次。
如果一次以上，那么我们就return s[0:next[n]]
否则，我们就看next[next[n]],只要这不为-1那就是正确答案。
为-1则不可能。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const  int max_n = 1e6 + 100;
int n;

int net[max_n];
void getnext(string p) {
    net[0] = -1;register int i = 0, j = -1;
    while (i < p.size()) {
        if (j == -1 || p[i] == p[j]) { net[++i] = ++j; }
        else j = net[j];
    }
}

int res[max_n];
int main() {
    ios::sync_with_stdio(0);
    string s;cin >> s;
    getnext(s);
    for (register int i = 1;i < s.size();++i)
        ++res[net[i]];
    int ans = net[s.size()];
    if (ans <= 0)
        cout << "Just a legend\n";
    else if (res[ans])
        cout << s.substr(0, ans) << endl;
    else if (net[ans] > 0)
        cout << s.substr(0, net[ans]) << endl;
    else
        cout << "Just a legend\n";
}