Manacher 알고리즘

팰린드롬 (Palindrome)

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

예를 들어 아래와 같다.

가장 긴 팰린드롬 구하기

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

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

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

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

BANANA

BANANA

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. 문자열을 왼쪽부터 하나씩 보면서,
2. 탐색 중인 위치(i)가 right 안쪽이라면,
3. 그다음, 남은 부분만 필요할 때만 확장 탐색한다.
4. 새로 찾은 팰린드롬이 기존보다 오른쪽으로 나가면 center, right를 갱신한다.

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

코드 예시

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)$이 된다