Manacher 알고리즘

2025-10-05

#알고리즘

3분

팰린드롬 (Palindrome)

팰린드롬은 문자열을 앞에서 읽으나 뒤에서 읽으나 동일한 형태로 읽히는 문자열을 의미한다.

예를 들어 아래와 같다.

순방향	역방향	팰린드롬 여부
abba	abba	O
abcba	abcba	O
abbcba	abcbba	X

가장 긴 팰린드롬 구하기

그렇다면 임의의 문자열에서 가장 긴 팰린드롬을 구하려면 어떻게 해야할까?

BANANA 라는 문자열을 생각해보자.

여기서 가장 긴 팰린드롬은 ANANA가 될 것이다.

팰린드롬을 가장 쉽게 구하는 방법은 아래 처럼 가운데부터 순차적으로 확인하는 것이다.

BANANA

각 인덱스마다 좌우를 확장하면서 비교하기 때문에 최악의 경우 모든 문자 쌍을 확인해야 한다.

따라서 시간 복잡도는 $O(N^2)$ 이 되어 문자열이 길어진다면 비효율적인 방법이 될 것이다.

Manacher 알고리즘

이러한 비효율성을 해결하기 위해 고안된 것이 바로 Manacher 알고리즘이다.

Manacher 알고리즘은 중복된 연산을 줄여 모든 위치에서의 팰린드롬 길이를 선형 시간 $O(N^2)$ 안에 계산할 수 있다.

덕분에 긴 문자열에서도 효율적으로 가장 긴 팰린드롬을 찾을 수 있다.

1. 아이디어: "대칭성을 이용하자"

우선 홀수 길이의 팰린드롬만 생각해보자.

홀수 팰린드롬은 항상 중심 문자를 기준으로 양쪽이 대칭이다.

예를 들어 BANANA의 ANANA를 보면,

B A N A N A ↑ 중심 (A)

A를 중심으로 왼쪽(N A)과 오른쪽(A N)이 대칭인 걸 볼 수 있다.

이제 우리는 각 문자를 중심으로 가장 긴 팰린드롬의 반지름 길이(양쪽으로 얼마나 확장되는지)를 구하고 싶다.

2. 기존 방식의 한계

보통은 중심을 하나씩 옮기면서 좌우를 비교한다.

하지만 이건 $O(N^2)$ 이 걸린다.

그래서 Manacher 알고리즘은 이미 구한 팰린드롬의 대칭성을 활용해서 불필요한 탐색을 건너뛴다.

3. 핵심 아이디어: "거울 위치"

지금까지 찾은 가장 긴 팰린드롬이 있다고 하자.

예를 들어,

•
현재까지 찾은 가장 긴 팰린드롬: A를 중심으로 한 ANANA

•
현재 살펴보는 문자: 그 오른쪽에 있는 다섯 번째 문자 N

B A N A N A

↑

(탐색 중인 문자)

이제 현재 중심 A을 기준으로 대칭되는 문자(거울 문자)를 찾아본다. 그 문자는 왼쪽의 N이다.

B A [N] A [N] A

↕ ↕

대칭 문자

왼쪽 N을 중심으로 한 팰린드롬의 길이는 이미 알고 있고, 현재 위치의 N은 그 팰린드롬의 안쪽에 있으므로 일부 길이는 그대로 사용할 수 있다.

즉, 이미 구한 대칭 정보를 이용해서 새로운 중심에서의 팰린드롬 길이를 빠르게 추정할 수 있다.

따라서 우리는 모든 문자를 처음부터 다시 비교하지 않아도 된다!

4. 알고리즘 동작 요약

1
문자열을 왼쪽부터 하나씩 보면서,
- •
  현재 중심(center)과 오른쪽 끝(right)을 기록한다.

2
탐색 중인 위치(i)가 right 안쪽이라면,
- •
  i의 거울 위치(mirror = 2 * center - i)를 이용해 팰린드롬 길이를 미리 복사한다.

3
그다음, 남은 부분만 필요할 때만 확장 탐색한다.

4
새로 찾은 팰린드롬이 기존보다 오른쪽으로 나가면 center, right를 갱신한다.

이 과정을 반복하면 모든 위치의 팰린드롬 길이를 한 번의 순회로 구할 수 있다.

코드 예시

Java

public static int manacher(String s) {
    // 1. 예외 처리
    if (s == null || s.length() <= 1) {
        return s.length();
    }

    int len = s.length();

    // 2. 전처리: 문자열 사이에 '#' 삽입 (짝수 팰린드롬 처리를 위해)
    // 예: "BANANA" → "*#B#A#N#A#N#A#@"
    StringBuilder sb = new StringBuilder(len * 2 + 3);
    sb.append('*');
    for (int i = 0; i < len; i++) {
        sb.append('#').append(s.charAt(i));
    }
    sb.append("#@"); // 끝 표시용 문자

    char[] T = sb.toString().toCharArray();
    int tLen = T.length;
    int[] P = new int[tLen]; // 각 인덱스에서의 팰린드롬 반지름 길이

    int center = 0, right = 0;
    int answer = 0;

    // 3. 메인 루프
    for (int i = 1; i < tLen - 1; i++) {
        int mirror = 2 * center - i; // 현재 중심에 대한 대칭 인덱스

        // 이미 탐색된 범위 안이라면, 대칭 위치의 결과를 일부 복사
        if (i < right)
            P[i] = Math.min(right - i, P[mirror]);
        else
            P[i] = 0;

        // 좌우 확장
        while (T[i - 1 - P[i]] == T[i + 1 + P[i]]) {
            P[i]++;
        }

        // right와 center 갱신
        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }

        // 최장 팰린드롬 길이 갱신
        answer = Math.max(answer, P[i]);
    }

    return answer;
}

6. 시간 복잡도는 왜 O(N)일까?

겉보기엔 여전히 각 문자마다 확장하니까 $O(N^2)$ 처럼 보일 수도 있다.

하지만 실제로는 그렇지 않다.

이유는 간단하다.

•
right는 항상 한 방향(오른쪽) 으로만 이동한다.

•
한 문자가 여러 번 확장 검사되는 일은 없다.

즉, 모든 문자에 대해 확장 시도는 최대 N번만 일어난다.

따라서 전체 시간 복잡도는 $O(N)$ 이 된다