| Task: | Longest palindrome |
| Sender: | aalto26iw_006 |
| Submission time: | 2026-11-04 16:20:57 +0200 |
| Language: | Rust (2021) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | ACCEPTED | 0.00 s | details |
| #3 | ACCEPTED | 0.05 s | details |
| #4 | ACCEPTED | 0.05 s | details |
| #5 | ACCEPTED | 0.05 s | details |
| #6 | ACCEPTED | 0.05 s | details |
| #7 | ACCEPTED | 0.05 s | details |
| #8 | ACCEPTED | 0.04 s | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | ACCEPTED | 0.00 s | details |
| #11 | ACCEPTED | 0.01 s | details |
| #12 | ACCEPTED | 0.00 s | details |
| #13 | ACCEPTED | 0.00 s | details |
| #14 | ACCEPTED | 0.00 s | details |
| #15 | ACCEPTED | 0.00 s | details |
| #16 | ACCEPTED | 0.02 s | details |
Code
#![allow(unused)]
use std::collections::*;
use std::io;
fn take_string() -> (Vec<char>, Vec<u8>) {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let vec: Vec<u8> = input.trim().as_bytes().to_vec();
(input.trim().chars().collect(), vec)
}
fn manacher(s: &Vec<u8>) -> Vec<usize> {
let n = 2 * s.len() + 3;
let mut ms: Vec<u8> = Vec::with_capacity(n);
let mut p: Vec<usize> = vec![0; n];
let (mut l, mut r) = (0usize, 0usize);
ms.push(b'@');
for i in 0..s.len() { ms.push(b'#'); ms.push(s[i]); }
ms.push(b'#');
ms.push(b'$');
for i in 1..n - 1 {
p[i] = if i < r { p[l + r - i].min(r - i) } else { 0 };
while ms[i + 1 + p[i]] == ms[i - 1 - p[i]]{
p[i] += 1;
}
if i + p[i] > r { l = i - p[i]; r = i + p[i]; }
}
p
}
fn longest_palindrome(s: &Vec<u8>) -> (usize, usize) {
let pal = manacher(s);
let mut best = (0, 0);
for (c, &len) in pal.iter().enumerate() {
if len > best.1 {
best = ((c - len - 1) / 2, len);
}
}
best
}
fn main() {
let (_, s) = take_string();
let (start, len) = longest_palindrome(&s);
println!("{}", std::str::from_utf8(&s[start..start + len]).unwrap());
}
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... |
