| Task: | Longest palindrome |
| Sender: | aalto26iw_004 |
| Submission time: | 2026-11-04 17:09:35 +0200 |
| Language: | Python3 (PyPy3) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.04 s | details |
| #2 | ACCEPTED | 0.04 s | details |
| #3 | ACCEPTED | 0.50 s | details |
| #4 | ACCEPTED | 0.44 s | details |
| #5 | ACCEPTED | 0.59 s | details |
| #6 | ACCEPTED | 0.59 s | details |
| #7 | ACCEPTED | 0.60 s | details |
| #8 | ACCEPTED | 0.39 s | details |
| #9 | ACCEPTED | 0.04 s | details |
| #10 | ACCEPTED | 0.04 s | details |
| #11 | ACCEPTED | 0.19 s | details |
| #12 | ACCEPTED | 0.04 s | details |
| #13 | ACCEPTED | 0.04 s | details |
| #14 | ACCEPTED | 0.04 s | details |
| #15 | ACCEPTED | 0.04 s | details |
| #16 | ACCEPTED | 0.26 s | details |
Code
s = input().strip()
n = len(s)
A = 911382323
B = (1 << 61) - 1
h = [0] * (n + 1)
r = [0] * (n + 1)
p = [1] * (n + 1)
for i in range(n):
h[i + 1] = (h[i] * A + ord(s[i])) % B
r[i + 1] = (r[i] * A + ord(s[n - 1 - i])) % B
p[i + 1] = p[i] * A % B
def is_palindrome(a, b):
if a < 0 or s[a] != s[b]:
return False
forward = h[b + 1] - h[a] * p[b - a + 1]
backward = r[n - a] - r[n - 1 - b] * p[b - a + 1]
return (forward - backward) % B == 0
best = 0
end = 0
for i in range(n):
if is_palindrome(i - best - 1, i):
best += 2
end = i
elif is_palindrome(i - best, i):
best += 1
end = i
print(s[end - best + 1:end + 1])
Test details
Test 1
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaa |
| correct output |
|---|
| aaaaaaaaaa |
| user output |
|---|
| aaaaaaaaaa |
Test 2
Verdict: ACCEPTED
| input |
|---|
| ababababab |
| correct output |
|---|
| ababababa |
| user output |
|---|
| ababababa |
Test 3
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| user output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
Test 4
Verdict: ACCEPTED
| input |
|---|
| ababababababababababababababab... |
| correct output |
|---|
| ababababababababababababababab... |
| user output |
|---|
| ababababababababababababababab... |
Test 5
Verdict: ACCEPTED
| input |
|---|
| aztdvxzjwxtrludymvpradgbdpgnrq... |
| correct output |
|---|
| aztdvxzjwxtrludymvpradgbdpgnrq... |
| user output |
|---|
| aztdvxzjwxtrludymvpradgbdpgnrq... |
Test 6
Verdict: ACCEPTED
| input |
|---|
| vvfigwwsyxbukedgcfyibvtbclybud... |
| correct output |
|---|
| vvfigwwsyxbukedgcfyibvtbclybud... |
| user output |
|---|
| vvfigwwsyxbukedgcfyibvtbclybud... |
Test 7
Verdict: ACCEPTED
| input |
|---|
| abaabaaaaaaabaababbbbbbabaaabb... |
| correct output |
|---|
| babbbabbbaabbbbaabbbbbbbbaabbb... |
| user output |
|---|
| babbbabbbaabbbbaabbbbbbbbaabbb... |
Test 8
Verdict: ACCEPTED
| input |
|---|
| txolestmgyepwrpofxyesjtsfkhjac... |
| correct output |
|---|
| yxnbaabnxy |
| user output |
|---|
| yxnbaabnxy |
Test 9
Verdict: ACCEPTED
| input |
|---|
| ihpohpzoffel |
| correct output |
|---|
| ff |
| user output |
|---|
| ff |
Test 10
Verdict: ACCEPTED
| input |
|---|
| flexflexvpqxierullgcfckjqflexf... |
| correct output |
|---|
| cfc |
| user output |
|---|
| cfc |
Test 11
Verdict: ACCEPTED
| input |
|---|
| aabbabaabbaababbabaababbaabbab... |
| correct output |
|---|
| abaababbaabbabaababbabaabbaaba... |
| user output |
|---|
| abaababbaabbabaababbabaabbaaba... |
Test 12
Verdict: ACCEPTED
| input |
|---|
| obsession |
| correct output |
|---|
| ses |
| user output |
|---|
| ses |
Test 13
Verdict: ACCEPTED
| input |
|---|
| abcxcbaxcba |
| correct output |
|---|
| abcxcba |
| user output |
|---|
| abcxcba |
Test 14
Verdict: ACCEPTED
| input |
|---|
| zzabc |
| correct output |
|---|
| zz |
| user output |
|---|
| zz |
Test 15
Verdict: ACCEPTED
| input |
|---|
| aaccaabbaaccaaccaabbaaccaa |
| correct output |
|---|
| aaccaabbaaccaaccaabbaaccaa |
| user output |
|---|
| aaccaabbaaccaaccaabbaaccaa |
Test 16
Verdict: ACCEPTED
| input |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| correct output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
| user output |
|---|
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
