[snippet] manacher.py

백준 13275번. 가장 긴 팰린드롬 부분 문자열에 대한 풀이를 Manacher's Algorithm의 스니펫 느낌으로 작성.

• 가장 긴 팰린드롬 부분 문자열을 구할 때 사용.

• 이해하는 데에는 https://ialy1595.github.io/post/manacher/ 글이 최고지만, 해당 링크의 방법으로 Python 코드를 그대로 짜는 경우 TLE라, 최적화된 방식으로 짜야 함.

import sys
input = lambda: sys.stdin.readline().rstrip()
# miis = lambda: map(int, input().split())

def manacher(s):
    s = "#" + "#".join(list(s)) + "#"
    len_s = len(s)
    ret = [0] * len_s # ret[i] : i를 중심으로 만들 수 있는 최장 Palindrome의 길이

    c, r = -1, -1
    for i in range(len_s):
        if i <= r:
            j = c - (i-c)
            ret[i] = min(ret[j], r-i)
        
        while 0 <= i-ret[i]-1 and i+ret[i]+1 < len_s:
            if s[i-ret[i]-1] != s[i+ret[i]+1]:
                break
            ret[i] += 1
        if r < i+ret[i]:
            c = i; r = i+ret[i]
    return ret

S = input()
A = manacher(S)
print(max(A))

TLE 코드(참고용)

이거 뭐, 더 하려면 Python에서 C++로 갈아타라는 건가.
최적화 빡세게 안 하면 바로 TLE를 받으니... 참

import sys
input = lambda: sys.stdin.readline().rstrip()
# miis = lambda: map(int, input().split())

def manacher(s):
    s = "#" + "#".join(list(s)) + "#"
    ret = [0] * len(s) # ret[i] : i를 중심으로 만들 수 있는 최장 Palindrome의 길이

    c, r = -1, -1
    for i in range(len(s)):
        if i > r:
            c = l = r = i # l(left)은 임시 변수
            while 0 <= l and r < len(s):
                if s[l] != s[r]:
                    break
                l, r = l-1, r+1
            r -= 1
            ret[i] = r-c
        else:
            j = c - (i-c)
            if ret[j] < r-i:
                ret[i] = ret[j]
            elif ret[j] > r-i:
                ret[i] = r-i
            else: # ret[j] == r-i
                c = l = r = i
                while 0 <= l and r < len(s):
                    if s[l] != s[r]:
                        break
                    l, r = l-1, r+1
                r -= 1
                ret[i] = r-c
    return ret

S = input()
A = manacher(S)
print(max(A))