-
Notifications
You must be signed in to change notification settings - Fork 0
/
13506.py
41 lines (36 loc) · 910 Bytes
/
13506.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def getZarr(string, z):
n = len(string)
x, y, i = 0, 0, 0
for k in range(1, n):
if k > y:
x, y = k, k
while y < n and string[y-x] == string[y]:
y += 1
z[k] = y - x
y -= 1
else:
i = k - x
if z[i] < y - k + 1:
z[k] = z[i]
else:
x = k
while y < n and string[y-x] == string[y]:
y += 1
z[k] = y - x
y -= 1
return z
string = str(input())
n = len(string)
z = getZarr(string, [0]*n)
answer = ""
for i in range(n):
if i + z[i] == n:
isTrue = False
for j in range(i):
if z[j] >= z[i]:
isTrue = True
break
if isTrue:
answer = string[i:]
break
print(-1 if answer == "" else answer)