链接
点击跳转
题解
首先看一下
n
e
x
t
[
n
]
next[n]
next[n]这个后缀是不是在之前出现过，如果出现过那答案就是他了
如果之前没出现过呢，那么
n
e
x
t
[
n
e
x
t
[
n
]
]
next[next[n]]
next[next[n]]这个后缀就是答案，因为
n
e
x
t
[
n
e
x
t
[
n
]
]
next[next[n]]
next[next[n]]这个后缀也是
n
e
x
t
[
n
]
next[n]
next[n]这个前缀的后缀
如果
n
e
x
t
[
n
e
x
t
[
n
]
]
=
=
0
next[next[n]]==0
next[next[n]]==0，那就是无解了
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 5000010
#define maxe 5000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct KMP
{
int n
, next
[maxn
], t
[maxn
];
void build(char *r
, int len
)
{
int i
, j
=0;
n
=len
;
for(i
=1;i
<=len
;i
++)t
[i
]=r
[i
]; t
[len
+1]=0;
for(i
=2;i
<=len
;i
++)
{
for(;j
and t
[j
+1]!=t
[i
];j
=next
[j
]);
next
[i
] = t
[j
+1]==t
[i
]?++j
:0;
}
}
int move(int pos
, int x
)
{
for(;pos
and t
[pos
+1]!=x
;pos
=next
[pos
]);
return t
[pos
+1]==x
? pos
+1 : 0;
}
}kmp
;
char r
[maxn
];
int main()
{
ll n
, i
, ans
=0;
scanf("%s",r
+1);
n
=strlen(r
+1);
kmp
.build(r
,n
);
rep(i
,1,n
-1)if(kmp
.next
[i
]==kmp
.next
[n
])ans
=kmp
.next
[n
];
if(!ans
)ans
= kmp
.next
[kmp
.next
[n
]];
if(ans
==0)printf("Just a legend");
else
{
rep(i
,1,ans
)printf("%c",r
[i
]);
}
return 0;
}
