김동호 블로그

Manacher 알고리즘

#알고리즘#Manacher 알고리즘

1. Manacher 알고리즘이란?

우리는 보통 주어진 문자열에서 최장 팰린드롬 문자열을 찾을 때, 문자열을 하나씩 순회하면서 탐색 인덱스를 중심으로 확장하는 방식을 사용합니다.

이 방식은 시간 복잡도가 O(N^2) 인데요. DP의 메모이제이션 기법을 사용하면 O(N) 만에 최장 팰린드롬 문자열의 길이를 구할 수 있는 알고리즘이 있습니다.

이것이 바로 Manacher 알고리즘입니다.

Manacher 알고리즘을 사용하면 문자열을 단 한 번만 훑는 것과 같은 선형 시간(O(N)) 내에 모든 팰린드롬을 찾을 수 있습니다.

2. 동작 방식

초기 문자열이 "abacaba" 라고 가정했을 때 Manacher 알고리즘의 동작 방식에 대해 이해해보겠습니다.

2.1. 전처리

가장 먼저 전처리 과정이 필요합니다.

팰린드롬 문자열의 길이가 홀수가 될수도, 짝수가 될수도 있는데 모든 회문을 홀수 길이로 통일하기 위한 작업입니다.
모든 문자 사이, 그리고 양끝에 특수 문자(예: #)를 끼워 넣음으로써 이 작업을 수행합니다.

  • aba → #a#b#a# (길이: 7)
  • abba → #a#b#b#a# (길이: 9)
  • abacaba -> #a#b#a#c#a#b#a# (길이: 15)

2.2. 핵심 변수 정의

Manacher 알고리즘의 세 가지 핵심 요소입니다.

  • P[i]: i번 인덱스를 중심으로 하는 최장 팰린드롬의 반지름 (중심 문자 제외)
  • C: 현재까지 발견된 팰린드롬 중 가장 오른쪽 끝(R)이 먼 팰린드롬의 중심점.
  • R: 그 팰린드롬의 오른쪽 끝 경계선 (R = C + P[C]).

2.3. 대칭성 활용

이 알고리즘의 시간 복잡도가 O(N)인 이유는 이미 구한 팰린드롬 정보를 재사용하기 때문입니다.

현재 위치 i에서 P[i]를 구할 때, i가 R 내부에 있다면 C를 기준으로 한 i의 대칭점 i' 의 정보를 가져옵니다. (i' = 2C - i)

2.4. 상황별 처리

  1. i'의 팰린드롬이 C의 범위 안에 완전히 포함될 때: P[i] = P[i']로 결정됩니다. 이때 추가 탐색이 필요없습니다.
  2. i'의 팰린드롬이 C의 범위를 벗어날 때: i에서 R 까지는 팰린드롬임이 보장되므로, P[i] = R - i 부터 시작해 하나씩 확장을 시도합니다.

2.5. Python 구현 예시

이제 이를 Python 코드로 구현하면 다음과 같습니다.

def manachers(s):
    # 1. 전처리 수행
    T = '#' + '#'.join(s) + '#'
    P = [0] * len(T)
    C = R = 0
    
    # 문자열을 한 번만 순회합니다.
    for i in range(len(T)):
        # 2. i가 R 내부인 경우 == 이전에 기록한 정보(P[i])를 이용해 빠르게 탐색 범위를 초기화할 수 있다.
        if i < R:
            # R - i: i부터 R까지의 길이입니다. L부터 R까지 (2*C)는 팰린드롬인 것이 밝혀졌기 때문에, i부터 R까지도 팰린드롬이 보장됩니다.
            # P[2*C - i]: C를 기준으로 현재 i의 반대편에 있는 인덱스 (i')의 최장 팰린드롬 길이입니다.
            # 둘 중 작은 값으로 하는 이유는, i'의 팰린드롬이 2*C 범위 밖으로 벗어나게 될 경우 P[i]는 P[i']와 같은 길이를 가질 수 없습니다. 아직 탐색을 하지 않은 R을 벗어나버리기 때문입니다. 따라서 확실한 값인 R - i을 포함한 min() 연산을 통해 확실한 값을 보장해주기 위함입니다. 
            P[i] = min(R - i, P[2*C - i])
        
        # 3. 중심을 확장합니다.
        while (i + P[i] + 1 < len(T) and i - P[i] - 1 >= 0) and (T[i + P[i] + 1] == T[i - P[i] - 1]):
            P[i] += 1
        
        # 4. 중심(C)과 경계(R)를 갱신합니다.
        if i + P[i] > R:
            C, R = i, i + P[i]
            
    # 원본 문자열 기준 최대 길이는 max(P)와 같습니다.
    return max(P)

2.6. 동작 순서

위 동작을 하나씩 살펴보면 아래 그림과 같습니다.
i가 이동함에 따라, C와 R이 어떻게 팰린드롬 범위를 확장하는지 주목해 보세요.

Manacher 알고리즘 동작 순서 시각화

2.7. 동작 방식 정리

한번에 이해하기 조금 어려울 수 있는데요. 문자열을 하나씩 순회하면서 탐색 중인 인덱스를 기준으로 양옆 범위를 넓혀가며 최장 길이의 팰린드롬 문자열을 찾고, 이를 P[i]에 기록한 다음(메모이제이션), 이후의 탐색 과정에서 이미 찾은 팰린드롬 범위의 안의 인덱스라면(i < R), 이전에 기록한 정보(P[i])를 이용해서 확실하게 팰린드롬이면서 탐색 생략이 가능한 부분을 건너띈 상태로 초기 탐색 범위를 초기화 하는 것 입니다.

3. 결과

위 동작 순서를 바탕으로 문자열을 딱 한 번만 순회하므로 시간 복잡도 O(N) 만에 문자열 s의 모든 팰린드롬을 찾을 수 있는 것입니다.

마찬가지로 공간 복잡도도 문자열의 길이에 패딩을 더한 길이만큼만 차지하면 됩니다.

© 2026 kdkdhoho. Built with Gatsby