마나처(Manacher) 알고리즘 – O(n) 선형 시간에 최장 팰린드롬 부분 문자열 찾기

마나처(Manacher) 알고리즘이란?

문자열에서 가장 긴 팰린드롬(palindrome) 부분 문자열을 찾을 때 마나처(Manacher) 알고리즘을 사용하면 선형 시간 안에 문제를 해결할 수 있습니다. 기본 접근은 각 문자를 중심으로 삼고 왼쪽·오른쪽 포인터를 확장해 가며 팰린드롬 여부를 확인하는 것이지만, 마나처 알고리즘은 이미 계산한 팰린드롬 정보를 별도의 배열(longPal)에 저장해 두었다가 재활용한다는 점이 결정적으로 다릅니다. 이를 통해 불필요한 문자 비교를 건너뛸 수 있으며, 전체 문자열을 한 번 순회한 뒤 배열의 최댓값만 확인하면 곧바로 최장 팰린드롬을 얻을 수 있습니다.

이 알고리즘의 시간 복잡도는 O(n)으로, 단순 중심 확장 방식(O(n²))보다 훨씬 효율적입니다.

핵심 아이디어

구분자 삽입: 문자 사이에 특수 문자(# 등)를 끼워 넣어 홀수 길이와 짝수 길이 팰린드롬을 동일한 로직으로 처리합니다. 의사 코드의 n := 2n+1이 바로 이 변환 과정입니다.
거울 대칭 활용: 현재 중심(centerIndex)을 기준으로 대칭되는 위치(left = 2*centerIndex − right)의 팰린드롬 정보를 가져와 초기값으로 사용합니다.
경계 관리: 지금까지 발견한 팰린드롬의 오른쪽 끝(rightIndex) 안에 있는 동안은 기존 정보를 재활용하고, 경계를 벗어날 때만 새로 확장하며 비교합니다.

입력 및 출력

입력:
문자열: "levelup"
출력:
가장 긴 팰린드롬: level

알고리즘

입력 − 최장 팰린드롬을 찾을 대상 문자열(text)

출력 − 해당 문자열에서 발견된 가장 긴 팰린드롬

Begin
    n := text size
    if n = 0, then
        return null string
    n := 2n+1

    define array longPal of size n
    longPal[0] := 0 and longPal[1] := 1
    centerIndex := 1
    rightIndex := 2
    right := 0
    maxPalLength := 0
    maxCenterIndex := 0
    start := -1 and end := -1, diff := -1

    for right := 2 to n-1, do
        left := 2*centerIndex – right
        longPal[right] := 0
        diff := rightIndex – right
        if diff > 0, then
            longPal[right] := minimum(longPal[left], diff)
            while (right + longPal[right]) < n AND (right - longPal[right]) > 0 AND
                  ((right + longPal[right]+1) mod 2 = 0 OR
                   text[(right + longPal[right] + 1)/2] = text[(right - longPal[right]-1)/2]), do
                increase longPal[right] by 1
            done

        if longPal[right] > maxPalLength, then
            maxPalLength := longPal[right]
            maxCenterIndex := right
        if (right + longPal[right]) > rightIndex, then
            centerIndex := right
            rightIndex := right + longPal[right]
    done
    start := (maxCenterIndex – maxPalLength)/2
    end := start + maxPalLength – 1

    palindrome = substring of text[start..end]
    return palindrome
End

순회가 끝나면 maxCenterIndex와 maxPalLength를 이용해 원본 문자열 상의 시작·끝 인덱스를 계산하고, 해당 구간을 잘라 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int min(int a, int b) {
    return (a<b)?a:b;
}

string longestPalindrome(string mainString) {
    int n = mainString.size();
    if(n == 0)
        return "";
    n = 2*n + 1; // 다음 위치 계산
    int longPal[n]; // 최장 팰린드롬 길이를 저장하는 배열
    longPal[0] = 0; longPal[1] = 1;
    int centerIndex = 1;
    int rightIndex = 2;
    int right = 0, left;
    int maxPalLength = 0, maxCenterIndex = 0;
    int start = -1, end = -1, diff = -1;

    for (right = 2; right < n; right++) {
        left  = 2*centerIndex-right; // 중심과 right로 left 위치 계산
        longPal[right] = 0;
        diff = rightIndex - right;

        if(diff > 0)
            longPal[right] = min(longPal[left], diff);
        while ( ((right + longPal[right]) < n && (right - longPal[right]) > 0) &&
            ( ((right + longPal[right] + 1) % 2 == 0) ||
            (mainString[(right + longPal[right] + 1)/2] == mainString[(right - longPal[right] - 1)/2] ))) {
            longPal[right]++;
        }

        if(longPal[right] > maxPalLength) {     // 최대 팰린드롬 길이 갱신
            maxPalLength = longPal[right];
            maxCenterIndex = right;
        }

        if (right + longPal[right] > rightIndex) {
            centerIndex = right;
            rightIndex = right + longPal[right];
        }
    }

    start = (maxCenterIndex - maxPalLength)/2;
    end = start + maxPalLength - 1;
    string palindrome;

    for(int i=start; i<=end; i++)
        palindrome += mainString[i];
    return palindrome;
}

int main(int argc, char *argv[]) {
    string mainString, palindrome;
    cout << "Enter String:";
    cin >> mainString;
    palindrome = longestPalindrome(mainString);
    cout << "Longest palindrome is: " << palindrome << endl;
}

실행 결과

Enter String: levelup
Longest palindrome is: level

"levelup"이라는 입력 문자열에는 "level"이라는 길이 5의 팰린드롬이 포함되어 있으므로, 알고리즘은 이를 정확히 찾아냅니다.