Longest palindrome

class manacher:

    def __init__(self, s):

        self.ms = "@"
        for c in s:
            self.ms += "#" + c
        self.ms += "#$"
        self.p = [0] * len(self.ms)
        self.runManacher()

    def runManacher(self):
        n = len(self.ms)
        l = r = 0

        for i in range(1, n - 1):
            mirror = l + r - i
            if 0 <= mirror < n:
                self.p[i] = max(0, min(r - i, self.p[mirror]))
            else:
                self.p[i] = 0


            while (i + 1 + self.p[i] < n and
                   i - 1 - self.p[i] >= 0 and
                   self.ms[i + 1 + self.p[i]] == self.ms[i - 1 - self.p[i]]):
                self.p[i] += 1

  
            if i + self.p[i] > r:
                l = i - self.p[i]
                r = i + self.p[i]


    def getLongest(self, cen, odd):
        pos = 2 * cen + 2 + (0 if odd else 1)
        return self.p[pos]


    def check(self, l, r):
        length = r - l + 1
        return length <= self.getLongest((l + r) // 2, length % 2)


def getLongestPal(s):
    n = len(s)
    maxLen = 1
    start = 0
    M = manacher(s)

    for i in range(n):
        oddLen = M.getLongest(i, 1)
        if oddLen > maxLen:
            start = i - (oddLen - 1) // 2

        evenLen = M.getLongest(i, 0)
        if evenLen > maxLen:
            start = i - (evenLen - 1) // 2

        maxLen = max(maxLen, max(oddLen, evenLen))

    return s[start:start + maxLen]


if __name__ == "__main__":
    s = input()
    print(getLongestPal(s))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: TIME LIMIT EXCEEDED