Longest palindrome

class Manacher:
    def __init__(self, s):
        self.transformed = '@#' + '#'.join(s) + '#$'
        self.pal_radii = [0] * len(self.transformed)
        self._process()

    def _process(self):
        n = len(self.transformed)
        center = right = 0

        for i in range(1, n - 1):
            mirror = 2 * center - i

            if i < right:
                self.pal_radii[i] = min(right - i, self.pal_radii[mirror])
            while self.transformed[i + 1 + self.pal_radii[i]] == self.transformed[i - 1 - self.pal_radii[i]]:
                self.pal_radii[i] += 1

            if i + self.pal_radii[i] > right:
                center = i
                right = i + self.pal_radii[i]

    def longest_radius(self, center_index, is_odd_length):
        transformed_pos = 2 * center_index + 2 + (0 if is_odd_length else 1)
        return self.pal_radii[transformed_pos]


def longestPalindrome(s):
    manacher = Manacher(s)
    n = len(s)

    max_length = 1
    start_index = 0

    for i in range(n):
        odd_len = manacher.longest_radius(i, True)
        if odd_len > max_length:
            max_length = odd_len
            start_index = i - max_length // 2

        even_len = manacher.longest_radius(i, False)
        if even_len > max_length:
            max_length = even_len
            start_index = i - max_length // 2 + 1

    return s[start_index:start_index + max_length]


if __name__ == "__main__":
    s = input().strip()
    print(longestPalindrome(s))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED