[438] 팰린드롬 부분 문자열(Manacher's algorithm)(파이썬 코드)

1. Manacher's algorithm

우리말로는 마나커, 마나허, 매내처 등으로 불리는 알고리즘입니다.

어떤 문자열에서 팰린드롬인 모든 부분 문자열을 \(\mathbf{O(n)}\)만에 찾을 수 있는 알고리즘입니다.

코드는 다음과 같습니다.

def manacher(S: str):
    S = "*"+ "".join([c+"*" for c in S])
    length = len(S)
    radius = [0] * length
    old_center = 0
    old_radius = 0
    for center in range(length):
        if old_center+old_radius < center:
            radius[center] = 0
        else:
            radius[center] = min(radius[old_center - (center-old_center)], (old_center+old_radius) - center)
        
        while center-radius[center]-1 >= 0 and \
            center+radius[center]+1 < length and \
            S[center-radius[center]-1] == S[center+radius[center]+1]:
            radius[center] += 1
        
        if old_center+old_radius < center+radius[center]:
            old_center = center
            old_radius = radius[center]

    for i in range(1, length, 2):
        for j in range(radius[i], -1, -2):
            print(S[i-j+1:i+j+1:2])

manacher("colossus")
# c
# o
# olo
# l
# o
# s
# s
# sus
# u
# s

2. 동작 원리

먼저 팰린드롬의 정보를 반지름으로 저장하는 방법을 알아봅시다.

팰린드롬의 중심 문자를 "축"이라고 하면, 축의 양쪽은 문자열이 대칭이므로 축에서 팰린드롬의 끝까지 거리를 "반지름"으로 표현할 수 있습니다.

 

만약 문자열의 0 번째 문자부터 차례대로 반지름을 구해서 저장해두었다고 해봅시다.

j 번째 문자를 축으로 반지름을 구할 때, 사용할 수 있는 이전 값은 두 가지입니다.

하나는 지금까지 구한 가장 먼 팰린드롬의 축(i)과 반지름이고,

다른 하나는 그 축을 중심으로 j와 대칭을 이루는 위치(2i-j)를 축으로 했을 때의 반지름입니다.

이 때, j 를 축으로 하는 반지름의, 보장되는 최소값을 별도의 연산 없이 바로 알 수 있습니다.

바로 앞의 두 가지 조건 중 최소값입니다.

이전에 탐색된 문자는 추가적인 별도의 연산 없이 바로 활용됩니다.

그 이후, 확인이 안 된 범위로 확장해가며 j를 축으로 하는 팰린드롬을 탐색해나갑니다.

이런 식으로 탐색하면 시간복잡도 \(\mathbf{O(n)}\)으로 팰린드롬인 모든 부분 문자열 확인이 가능합니다.

 

이 과정에서 길이가 짝수인 문자열은 중심 축이 되는 문자가 없으므로 문자열 사이사이에 임의의 문자(보통은 "*" 이나 "?" 등을 사용)를 끼워넣어 홀수로 만들어 계산하면 됩니다.

def manacher(S: str):
    S = "*"+ "".join([c+"*" for c in S]) # 문자 사이사이에 * 추가
    length = len(S)
    radius = [0] * length # 반지름을 관리할 배열

    # 이전까지 최대범위를 가지는 팰린드롬 관리할 변수
    old_center = 0
    old_radius = 0
    
    for center in range(length):
        if old_center+old_radius < center: # 범위 밖이면
            radius[center] = 0
        else:
            radius[center] = min(radius[old_center - (center-old_center)], (old_center+old_radius) - center)
        
        # 현재 축으로 가능한 최대범위 팰린드롬 탐색
        while center-radius[center]-1 >= 0 and \
            center+radius[center]+1 < length and \
            S[center-radius[center]-1] == S[center+radius[center]+1]:
            radius[center] += 1
        
        # 최대범위 수정
        if old_center+old_radius < center+radius[center]:
            old_center = center
            old_radius = radius[center]


	# 부분 문자열 중 팰린드롬을 출력하는 2중 for문
    for i in range(1, length, 2):
        for j in range(radius[i], -1, -2):
            print(S[i-j+1:i+j+1:2])

manacher("colossus")
# c
# o
# olo
# l
# o
# s
# s
# sus
# u
# s

 

이 알고리즘으로 해결 가능한 문제: 가장 긴 팰린드롬 부분 문자열

https://www.acmicpc.net/problem/13275