Manacher's Algorithm

소개

Manacher's 알고리즘은 문자열 내에서 가장 긴 팰린드롬을 찾는데 특화되어 있는 알고리즘이다.

만약 위 문제를 브루트포스 방식으로 접근한다면 $O(n^2)$의 시간 복잡도를 가질 것이다.

하지만 Manacher 알고리즘을 사용하면 $O(n)$ 시간으로 문제 해결이 가능하다.

원리

0. 주어진 문자열의 문자들 사이에 특수문자를 추가 (예: banana -> #b#a#n#a#n#a#)

아래 방법은 홀수 팰린드롬만 계산할 수 있기 때문에 이를 해결해주기 위해 문자열 사이에 특수 문자를 추가해준다.

1. 주어진 문자열 S와 동일한 길이의 배열 A를 생성, 초기값을 전부 0으로 설정.

2. 팰린드롬의 반지름 r, 중점 p의 초기값을 0으로 설정

3. 문자열의 인덱스 i에 대하여 다음을 수행

• i > r 일시: A[i]=0
• i ≤ r일시: A[i]=min(A[2p-i],r-i) 로 초기화하고 S[i-A[i]]=S[i+A[i]]을 만족하는 A[i]의 최댓값을 A[i]로 설정
  (2p-i는 i를 p에 대해 대칭시킨 위치)
• 반지름 r 보다 i+A[i]가 클 시 r과 p를 업데이트

코드

def manachers(s):
    s='#'+'#'.join(list(s))+'#'
    n=len(s)
    a=[0]*n 
    r,p,m=0,0,0
    for i in range(n):
        if i<=r: a[i] = min(a[2*p-i], r-i)
        while i-a[i]-1>=0 and i+a[i]+1<n and s[i-a[i]-1]==s[i+a[i]+1]:
            a[i]+=1
        if r<i+a[i]:
            r=i+a[i]
            p=i
        m=max(m,a[i])
    return m

위 코드는 가장 긴 팰린드롬의 최대 길이를 반환하게 만든 코드이다.