Submission details
Task:Longest palindrome
Sender:aalto26iw_003
Submission time:2026-11-04 16:24:35 +0200
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#10.05 sdetails
#20.05 sdetails
#30.28 sdetails
#40.28 sdetails
#50.31 sdetails
#60.31 sdetails
#70.31 sdetails
#80.27 sdetails
#90.05 sdetails
#100.05 sdetails
#110.12 sdetails
#120.05 sdetails
#130.05 sdetails
#140.05 sdetails
#150.05 sdetails
#160.15 sdetails

Code

# FULL TEMPLATE: delete every block you don't use. Blocks don't depend on each other.
# Nodes are 1..n (slot 0 unused). Arrays are 0-indexed.
import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from itertools import accumulate, permutations, combinations, product
from functools import lru_cache, cmp_to_key
from math import gcd, isqrt, comb, inf
input = sys.stdin.readline
MOD = 10**9 + 7

def I():  return int(input())                    # "5"          -> 5
def MI(): return map(int, input().split())       # "8 4"        -> n, q = MI()
def LI(): return list(map(int, input().split())) # "3 2 4 5"    -> [3, 2, 4, 5]
def S():  return input().strip()                 # "BABAZA", ".*.#" (kept as text)
def LS(): return input().split()                 # "? 2 3"      -> ['?', '2', '3']

def manacher(s):  # -> p on t = "#a#b#a#": p[i] = radius in t = LENGTH of the palindrome in s
    t = "#" + "#".join(s) + "#"           # every palindrome in t has odd length: one case only
    n = len(t)
    p = [0] * n
    c = r = 0                             # palindrome t[c-p[c] .. c+p[c]] reaches furthest right (r)
    for i in range(n):
        if i < r:
            p[i] = min(r - i, p[2 * c - i])   # mirror image of i around c
        while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]:
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
    return p 

def longest_palindrome(s):
    p = manacher(s)
    i = max(range(len(p)), key=p.__getitem__)
    start = (i - p[i]) // 2
    return s[start:start + p[i]]

def main():
    s = S()
    p = manacher(s)
    i = max(range(len(p)), key=p.__getitem__)
    start = (i - p[i]) // 2
    return s[start:start + p[i]]


main()

Test details

Test 1

Verdict:

input
aaaaaaaaaa

correct output
aaaaaaaaaa

user output
(empty)

Test 2

Verdict:

input
ababababab

correct output
ababababa

user output
(empty)

Test 3

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
(empty)

Test 4

Verdict:

input
ababababababababababababababab...

correct output
ababababababababababababababab...

user output
(empty)

Test 5

Verdict:

input
aztdvxzjwxtrludymvpradgbdpgnrq...

correct output
aztdvxzjwxtrludymvpradgbdpgnrq...

user output
(empty)

Test 6

Verdict:

input
vvfigwwsyxbukedgcfyibvtbclybud...

correct output
vvfigwwsyxbukedgcfyibvtbclybud...

user output
(empty)

Test 7

Verdict:

input
abaabaaaaaaabaababbbbbbabaaabb...

correct output
babbbabbbaabbbbaabbbbbbbbaabbb...

user output
(empty)

Test 8

Verdict:

input
txolestmgyepwrpofxyesjtsfkhjac...

correct output
yxnbaabnxy

user output
(empty)

Test 9

Verdict:

input
ihpohpzoffel

correct output
ff

user output
(empty)

Test 10

Verdict:

input
flexflexvpqxierullgcfckjqflexf...

correct output
cfc

user output
(empty)

Test 11

Verdict:

input
aabbabaabbaababbabaababbaabbab...

correct output
abaababbaabbabaababbabaabbaaba...

user output
(empty)

Test 12

Verdict:

input
obsession

correct output
ses

user output
(empty)

Test 13

Verdict:

input
abcxcbaxcba

correct output
abcxcba

user output
(empty)

Test 14

Verdict:

input
zzabc

correct output
zz

user output
(empty)

Test 15

Verdict:

input
aaccaabbaaccaaccaabbaaccaa

correct output
aaccaabbaaccaaccaabbaaccaa

user output
(empty)

Test 16

Verdict:

input
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

correct output
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

user output
(empty)