매내처 알고리즘 (Manacher's Algorithm)

정의

매내처 알고리즘 (Manacher’s Algorithm) 은 문자열 s[0..N-1] 의 모든 위치에서 중심으로 하는 최장 회문 (palindrome) 반지름 을 O(N) 시간에 계산하는 선형 알고리즘. Glenn Manacher 가 1975년에 고안.

결과 배열 d[i] 는:

• 홀수 길이 회문: d1[i] = 중심 i 에서 반지름 (좌우 r 칸씩)
• 짝수 길이 회문: d2[i] = 중심 i-1, i 사이에서 반지름

최장 회문 부분 문자열 찾기: naive O(N^2), DP O(N^2), 매내처 O(N).

문제 상황과 동기

길이 N 문자열의 가장 긴 회문 부분 문자열 을 찾는다.

• naive: 모든 중심 위치 (N개) × 최대 반지름 (N) 확인. O(N^2). N=10^5 면 10^10, 불가.
• DP: dp[i][j] = s[i..j] 가 회문인지. O(N^2) 시간/공간.
• 매내처: O(N) 시간, O(N) 공간.

핵심 통찰: 이미 계산된 회문 범위 (palindrome box) 를 대칭 재사용. amortized O(N).

PS 뿐 아니라 DNA 서열 분석, 압축 같은 실무 문자열 처리에도 사용.

시각화

핵심 아이디어

palindrome box: 지금까지 가장 오른쪽으로 뻗은 회문 [l, r] (중심 c).

invariant: r = max { i + d[i] } (지금까지)

새 i 계산:

1. i > r: naive 확장 시작. 중심 i 에서 좌우 비교하며 d[i] 갱신, (c, l, r) 갱신.
2. i ≤ r: s[i..r] 는 s[l..i] 와 대칭 (c 기준). 대칭 위치 j = c - (i - c) 의 d[j] 재사용:
   • d[j] < r - i: d[i] = d[j] (재사용 가능)
   • d[j] ≥ r - i: r 너머 확장 시도 필요, naive 비교로 연장

홀수 / 짝수 회문 처리:

• 방법 1: 두 배열 d1, d2 각각 계산
• 방법 2: 문자 사이 dummy # 삽입 → s = "#a#b#c#" → 한 배열로 통합

방법 2 가 구현 간결, 대부분 채택.

amortized O(N): r 은 최대 2N-1 (dummy 포함 길이) 까지 증가, 한 번 증가하면 감소 안 함. 총 비교 O(N).

알고리즘

manacher(s):
    # 홀수/짝수 통합: 문자 사이 '#' 삽입
    t = "#" + "#".join(s) + "#"
    N = len(t)
    d = [0] * N
    l, r = 0, -1
    for i = 0 to N-1:
        if i > r:
            k = 0
        else:
            j = l + r - i
            k = min(d[j], r - i)
        while i - k >= 0 and i + k < N and t[i - k] == t[i + k]:
            k++
        d[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    return d

longest_palindrome(s):
    d = manacher(s)
    max_len = max(d)
    center = d.index(max_len)
    # t 에서 [center - max_len + 1, center + max_len - 1] 추출
    # 원본 s 로 변환

구현

// Manacher: O(N) longest palindrome
#include <bits/stdc++.h>
using namespace std;
vector<int> manacher(const string& s) {
  string t = "#";
  for (char c : s) { t += c; t += '#'; }
  int n = t.size();
  vector<int> d(n);
  int l = 0, r = -1;
  for (int i = 0; i < n; i++) {
      int k = (i > r) ? 0 : min(d[l + r - i], r - i);
      while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;
      d[i] = k;
      if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
  }
  return d;
}
int main() {
  string s; cin >> s;
  auto d = manacher(s);
  int mx = *max_element(d.begin(), d.end());
  int c = find(d.begin(), d.end(), mx) - d.begin();
  int start = (c - mx + 1) / 2, len = mx - 1;
  cout << s.substr(start, len) << "\n";
}

# Manacher in Python (O(N))
def manacher(s):
  t = '#' + '#'.join(s) + '#'
  n = len(t)
  d = [0] * n
  l, r = 0, -1
  for i in range(n):
      k = 0 if i > r else min(d[l + r - i], r - i)
      while i - k >= 0 and i + k < n and t[i - k] == t[i + k]:
          k += 1
      d[i] = k
      if i + k - 1 > r:
          l, r = i - k + 1, i + k - 1
  return d
​
s = input().strip()
d = manacher(s)
mx = max(d)
c = d.index(mx)
start = (c - mx + 1) // 2
length = mx - 1
print(s[start : start + length])

// Manacher in Java
import java.util.*;
public class Main {
  static int[] manacher(String s) {
      StringBuilder t = new StringBuilder("#");
      for (char c : s.toCharArray()) { t.append(c).append('#'); }
      int n = t.length();
      int[] d = new int[n];
      int l = 0, r = -1;
      for (int i = 0; i < n; i++) {
          int k = (i > r) ? 0 : Math.min(d[l + r - i], r - i);
          while (i - k >= 0 && i + k < n && t.charAt(i - k) == t.charAt(i + k)) k++;
          d[i] = k;
          if (i + k - 1 > r) { l = i - k + 1; r = i + k - 1; }
      }
      return d;
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      String s = sc.next();
      int[] d = manacher(s);
      int mx = 0, c = 0;
      for (int i = 0; i < d.length; i++) {
          if (d[i] > mx) { mx = d[i]; c = i; }
      }
      int start = (c - mx + 1) / 2, len = mx - 1;
      System.out.println(s.substring(start, start + len));
  }
}

abacabad

abacaba

cbbd

bb

복잡도

변형 / 활용

1. 회문 개수 세기

각 중심 i 에서 d[i] 개 회문 존재. 총 회문 개수 = Σ d[i]. O(N).

2. 최장 회문 접두사 / 접미사

d[i] 에서 i - d[i] + 1 == 0 (접두사) 또는 i + d[i] - 1 == 2N-1 (접미사) 찾기.

3. 회문 분할

문자열을 k 개 회문으로 분할하는 최소 k. DP + 매내처. O(N^2) (DP 부분).

4. 다이아몬드 회문

중심에서 여러 겹 회문. 매내처로 각 위치 회문 확인 후 재귀 탐색.

함정

1. dummy 문자 인덱스 변환

t = "#a#b#c#" 에서 d[i] 가 원본 s 의 어디인지 헷갈림.

원본 인덱스 = (t_index - 1) / 2
회문 길이 = d[i] - 1

구현할 때 start = (c - mx + 1) / 2, length = mx - 1 공식 정확히.

2. r < l 상태

초기 l=0, r=-1 일 때 i > r 조건 제대로 처리 안 하면 버그. r 초기값 -1 또는 0 잘 선택.

3. 짝수 회문 누락

dummy 없이 d1, d2 두 배열로 구현 시 짝수 회문 놓침. dummy 방식이 안전.

4. 중복 확장

while (i - k >= 0 && ...) 루프가 amortized O(N) 임을 신뢰 못하고 불필요 최적화. 그대로 두기.

5. 회문 길이 계산

d[i] 는 반지름, 실제 회문 길이는 d[i] - 1 (dummy 포함). 또는 dummy 길이 2*d[i] - 1 에서 dummy 제거.

응용 예제

BOJ 10066, 팰린드롬

모든 위치의 최장 회문 길이를 묻는 대표 문제. 매내처 직접 적용.

BOJ 13275, 가장 긴 팰린드롬 부분 문자열

단순 최장 회문. 매내처로 O(N).

접두사 회문 + 접미사 회문

d[i] 에서 i - d[i] + 1 == 0 인 최대 d[i] 찾기.

BOJ 연습 문제

참고

• Z 알고리즘 (prefix LCP O(N))
• KMP 알고리즘 (패턴 매칭 O(N+M))
• 문자열 해싱 (확률적 회문 판정)
• 동적 계획법 (O(N^2) 회문 판정)