发这个题解只是因为…大多数人的 Z 函数解法复杂度根本不对…
以下是这题用 Z 函数各种不对的复杂度做法：
1、枚举每一个后缀，通过 Z 可以求出与前缀的 LCP 然后去串里面暴力找子串。
2、枚举每一个中间串，通过 Z 可以求出与前缀的 LCP ，将这些长度暴力染色，遇到后缀就判一下。
……然后这两种复杂度都不对。考虑怎么优化一下。发现我们只关心最长能够匹配的前缀，因为前缀是固定的。于是记录一下这个最大值就好了。复杂度线性。
```cpp
namespace Z_F{
int L ;
int Q ;
int l, r ;
int Z[N] ;
int Pz[N] ;
void gao(int bg, int L){
for (int i = bg ; i < bg + L ; ++ i) Z[i] -- ;
Z[bg] = L ;
}
int get_Z(char *s, int bg, int oo = 0){
L = strlen(s + bg) ;
l = bg, r = 0 ; Z[bg] = 0 ;
for (int i = bg + 1 ; i < bg + L ; ++ i){
if (r < i) Z[i] = 1 ;
else Z[i] = min(Z[i - l + 1], r - i + 1) ;
while (s[Z[i]] == s[i + Z[i] - 1]) ++ Z[i] ;
if (r < i + Z[i] - 1) r = i + Z[i] - 1, l = i ;
}
if (!oo) gao(bg, L) ;
return L ;
}
int exKMP(char *s, int bg, char *t, int gb){
int q = get_Z(s, bg, 1) ; s[q + 1] = '#' ;
L = strlen(t + gb) ; l = gb, r = 0 ;
for (int i = gb ; i < gb + L ; ++ i){
if (r < i) Pz[i] = 1 ;
else Pz[i] = min(Z[i - l + 1], r - i + 1) ;
while (s[Pz[i]] == t[i + Pz[i] - 1]) ++ Pz[i] ;
if (r < i + Pz[i] - 1) r = i + Pz[i] - 1, l = i ;
}
for (int i = gb ; i < gb + L ; ++ i) Pz[i] -- ;
return L ;
}
}
int mx ;
int res ;
int Z1[N] ;
int Z2[N] ;
int tmp[N] ;
int ans[N] ;
int n, p ;
char s[N] ;
char t[N] ;
using namespace Z_F ;
int main(){
scanf("%s", s + 1) ;
n = get_Z(s, 1) ; res = 0 ;
for (int i = 2 ; i <= n ; ++ i){
if (i + Z[i] - 1 == n && Z[i] <= mx)
if (res < Z[i]) res = Z[i], p = i ;
chkmax(mx, Z[i]) ;
}
if (!res)
return puts("Just a legend"), 0 ;
for (int i = p ; i <= p + res - 1 ; ++ i)
putchar(s[i]) ; return puts(""), 0 ;
}
```