Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import sys
def kmp_init(P):
F = [0] * (len(P)+1)
i, j = 1, 0
while i<len(P):
if P[i] == P[j]:
i += 1; j += 1; F[i] = j
elif j == 0:
i += 1; F[i] = 0
else:
j = F[j]
return F
def kmp_suffix(P, T):
F = kmp_init(P)
i, j = 0, 0
n, m = len(T), len(P)
while i < n:
while i < n and j < m:
if P[j] == T[i]:
i += 1; j += 1
else:
break
if j == 0: i += 1
if i == n: return j
j = F[j]
return 0
data = sys.stdin.read().splitlines()
for s in data:
r = s[::-1]
print(len(s)*2-kmp_suffix(s, r))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.