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

不久他们发现了一个字符串S（|S|<=1000000），刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码，于是就大声将字符串朗读了出来，然而并没有什么事发生。于是Asterix又猜想密码一定是字符串S的子串T。

Prefix认为T是S的前缀，Suffix认为T是S的后缀，Obelix却认为T应该是S中的某一部分，也就是说，T既不是S的前缀，也不是S的后缀。

Asterix选择子串T来满足所有伙伴们的想法。同时，在所有可以被接受的子串变形中，Asterix选择了最长的一个（因为Asterix喜欢长的字符串）当Asterix大声读出子串T时，寺庙的大门开了。 （也就是说，你需要找到既是S的前缀又是S的后缀同时又在S中间出现过的最长子串）

现在给你字符串S，你需要找到满足上述要求的子串T。

题目类型：KMP，字符串

解题目标：找到最大的符合要求的子序列，使其既是前缀又是后缀，同时在字符串中间出现；

解题思路：1.用一遍KMP获得最长的前缀和后缀。

                  2.寻找在字符串的真子串（少最后几位）中最长的前缀和后缀长度，并记录，实际上是在找前缀和中间字串相等的最大长度；

                  3.从最大前缀长度为起点开始，如果当前能跳跃的最大距离 > z最大前缀与中间字串的长度，说明还未找到答案，因为答案应当是min(最长的前缀和后缀长度, 最长前缀与中间字串的长度），因此利用j = ne[j]得到下一个跳跃跨度并且继续比较，直到出线一个跳跃跨度 <= 最大前缀与中间字串的长度时，跳出，从头开始遍历长度为当前这个跳跃跨度长度的字符串输出；

AC代码：
 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
 int ne[N];
int main()
{
	string a;
	cin>>a;
	int len = a.length();
	a = ' '+a;

		for(int i = 2, j = 0; i<=len; i++)
		{
			while(j && a[i] != a[j+1]) j = ne[j];
			if(a[i] == a[j+1]) j++;
			ne[i] = j;
		}
	
		//int maxn = *max_element(ne+2,ne+len);//我也不明白，为啥用这句会RE，我寻思着我也没写错，离谱
		int maxn = 0;
		for(int i = 2; i<=len-1; i++) if(maxn < ne[i]) maxn = ne[i];
		
		int j = ne[len];
		while(j > maxn) j = ne[j];
		
		if(j == 0)
		{
			cout<<"Just a legend"<<endl;
		}else 
		{
			for(int i = 1; i<= j; i++) cout<<a[i];
		}
	
	return 0;
}