题目链接：http://codeforces.com/problemset/problem/126/B
题目大意：
多组数据
每组给定1个字符串S，问是否存在S的一个尽量长的子串，同时是S的前缀和后缀，并且在S的中间出现过（即非前缀也非后缀）。
分析：
利用KMP的next数组。
首先next[i]表示该位（不包括）往前数next[i]位恰好构成字符串S的一个前缀，假设字符串长度为len，那next[len]就表示S长为next[len]的后缀正好是S的前缀，恰好就是题目说的公共前后缀，于是想知道S中间有没有这个公共前后缀只要搜一遍next数组，从1~len-1，看有没有等于next[len]，如果有就输出S的前next[len]个字符，没有就输出"Just a legend"。
不过上面的方法存在漏铜，对于有的情况，自然是没问题的；对于没有的情况，就有疏漏：
对于字符串“abdabsab”，next数组为{-1,0,0,0,1,2,0,1,2}，显然是可以的；
而对于字符串“abfabdabeabfab”，next数组为{-1,0,0,0,1,2,0,1,2,0,1,2,3,4,5}，在这个案例里找5当然是找不到的，但确实存在子串“ab”，在开头结尾中间都出现过。在这种情况下，答案如果存在，它必然同时是“abfab”的前缀和后缀，也就是再让“abfab”自己和自己玩一次找公共前后缀得到长度为2，然后在next数组里搜2才行。那也就是说要递归？其实不用，设p = len，令p = next[p]，直接在next中查p即可，还查不到就在做一次p = next[p]，继续查，直到找到或找不到（p < 0）。这是为什么呢？原因还是“abfab”自己和自己玩，只不过这个“abfab”是开头那个，而p此时正好就是“abfab”再后一位的next值，直接就变成了求子问题，不需要递归。
代码如下：
#include <bits/stdc++.h>
using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a)) #define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} typedef long long LL;
const int maxN = 1e5 + ; string s; void KMP_next(string &T, vector< int > &nxt) {
nxt.resize(T.size() + );
nxt[] = -; int t = -, i = ;
while(i < T.size()) {
( > t || T[i] == T[t]) ? nxt[++i] = ++t : t = nxt[t];
}
} int main(){
while(cin >> s) {
string ans = "";
vector< int > nxt;
KMP_next(s, nxt);
unordered_set< int > si;
rep(i, nxt.size() - ) si.insert(nxt[i]); int p = nxt[nxt.size() - ];
while(p > ) {
if(si.find(p) != si.end()) {
ans = s.substr(, p);
break;
}
p = nxt[p];
} if(ans == "") cout << "Just a legend\n";
else cout << ans << endl;
} return ;
}