Manacher 알고리즘으로 최장 팰린드롬 부분문자열 찾기

최장 팰린드롬을 찾을 때 중심 확장이 반복되는 이유

최장 팰린드롬 부분문자열(Longest Palindromic Substring, LPS)은 입력 문자열 s에서 앞뒤가 같은 연속 부분문자열 가운데 가장 긴 구간과 길이를 찾는 문제다. aba처럼 한 문자를 중심으로 하는 경우와 abba처럼 두 문자 사이를 중심으로 하는 경우를 모두 고려해야 한다.

브루트포스, 중심 확장, 동적 계획법으로도 풀 수 있지만 긴 문자열에서는 비용이 커진다. Manacher 알고리즘은 이미 검사한 팰린드롬의 대칭 정보를 재사용해 이 문제를 O(n) 시간에 처리한다. 검색, 생명정보학, 에디터 기능, 데이터 전처리처럼 대규모 문자열을 다루는 경로에서 검토할 수 있는 방식이다.

전처리한 문자열에서 반경을 관리한다

핵심은 원본 문자열 사이에 구분자를 넣어 홀수와 짝수 팰린드롬을 같은 형태로 만드는 데 있다. 시작과 끝에는 센티넬을 붙여 확장 과정의 경계 검사를 줄인다.

전처리 문자열의 각 위치 i에는 그 위치를 중심으로 확장 가능한 최대 반경 P[i]를 기록한다. 현재까지 가장 오른쪽으로 확장된 구간의 중심을 Center, 오른쪽 경계를 Right로 두면, i < Right인 위치에서는 대칭 위치의 값을 초기 반경으로 활용할 수 있다.

P[i]는 전처리 문자열에서 i를 중심으로 한 최대 반경 길이다.
i < Right이면 P[i] = min(P[mirror(i)], Right - i)로 시작한 뒤, 일치하는 문자가 있으면 더 확장한다.
i + P[i] > Right가 되면 Center = i, Right = i + P[i]로 갱신한다.

이 방식에서는 이미 확인된 팰린드롬의 미러링 정보를 이용하므로 같은 비교를 반복하지 않는다. 각 문자는 최대 한 번의 확장에 기여하며, 전체 비교 횟수의 상한은 선형 수준으로 관리된다.

입력 검증부터 결과 역투영까지의 흐름

⤢✕

빈 문자열은 빈 결과로 처리하고, None 또는 비문자열 입력은 타입 검증 대상이다. 또한 전처리에 쓰는 구분자와 센티넬이 입력에 들어오지 않도록 사전에 보장하거나 런타임에 검사해야 한다.

최대 반경을 얻은 뒤 원본 문자열의 시작 위치는 start = (centerIndex - maxLen) // 2로 역투영한다. 이 인덱스 변환은 전처리와 결과 복원 사이에서 가장 먼저 검증할 지점이다.

중심 확장과 DP를 선택하는 경우

알고리즘	성능(시간복잡도)	확장성(입력 길이)	일관성(정확성)	안정성(엣지 케이스)	운영 편의(구현/디버깅)
Manacher	O(n)	대규모 n에서도 안정 동작	결정적, 전처리로 홀짝 통합	센티넬/구분자 관리 필요	중간 난이도, 인덱스 변환 주의
중심 확장	O(n^2) 최악	긴 문자열에서 성능 저하	결정적	구현 단순, 엣지 처리 용이	구현·디버깅 용이
DP 기반	O(n^2) 시간, O(n^2) 공간	대규모 n에서 메모리 병목	결정적	초기화/경계 조건 복잡	구현 복잡, 메모리 부담

중심 확장은 구현과 디버깅이 단순한 기준선이 될 수 있다. 반면 입력 길이가 커지고 반복 탐색 비용이 문제가 되는 상황에서는 Manacher의 전처리와 반경 관리가 더 적합하다. DP는 시간뿐 아니라 O(n^2) 공간을 요구하므로 대규모 입력에서 메모리 병목을 고려해야 한다.

문자열 처리 파이프라인에서의 활용

생명정보학에서는 DNA/RNA 서열의 회문성 모티프 탐지와 프라이머 설계를 지원하는 데 활용할 수 있다. 긴 서열을 처리할 때 선형 시간 탐색은 파이프라인 처리량에 영향을 준다.

텍스트 에디터나 IDE에서는 실시간 팰린드롬 하이라이트에 연결할 수 있으며, 문제 출제·채점 플랫폼의 런타임 제약에도 대응할 수 있다. 코드 골프나 퍼즐 검증 도구도 통합 대상이 된다.

데이터 전처리와 품질 검증에서는 토큰이나 로그의 대칭 패턴을 찾아 포맷 이상치를 탐지하는 용도로 쓸 수 있다. 압축이나 토큰화 이전의 패턴 분석 단계에도 적용 가능하다.

긴 입력에서 달라지는 비용과 메모리

n=10^6일 때 중심 확장이나 DP의 최악 연산량은 O(n^2)=10^12회 수준으로 실용 불가이며, 선형 알고리즘은 ≈ 10^6~몇×10^6 비교 수준으로 수 초 내 처리 가능성을 확보한다. 동일 하드웨어에서는 3~6자릿수 배의 처리량 향상을 기대할 수 있다.

반경 배열의 길이는 ≈ 2n+3이다. 32비트 정수를 사용할 경우 n=10^6에서 메모리는 ≈ 4바이트×(2,000,003) ≈ 8MB이며, 문자열을 포함해 총 수십 MB 내에서 관리할 수 있다. 이는 DP의 O(n^2) 메모리와 대비된다.

결정적인 결과와 예측 가능한 시간·메모리 상한은 SLA를 맞추는 데 유리하다. 입력 검증과 센티넬 전략을 표준화하면 엣지 케이스 누락도 줄일 수 있다.

Python 구현

전제조건: Python 3.10+, 표준 라이브러리만 사용. 입력은 파이썬 문자열(유니코드 코드 포인트 단위)로 가정한다. 그라페메 단위가 필요하면 별도 분할이 필요하다.

from typing import Tuple

def longest_palindromic_substring_manacher(s: str) -> str:
    """
    Manacher's Algorithm 구현
    - 입력: 임의의 문자열 s
    - 출력: s의 가장 긴 팰린드롬 부분문자열
    주의: 구분자('#')와 센티넬('^', '$')이 s에 포함되지 않는다고 가정
    """
    if not isinstance(s, str):
        raise TypeError("input must be str")
    if not s:
        return ""

    # 전처리: 홀짝 통합, 경계 보호
    t = "^#" + "#".join(s) + "#$"
    n = len(t)
    P = [0] * n
    center = right = 0

    for i in range(1, n - 1):
        mirror = 2 * center - i
        if i < right:
            P[i] = min(right - i, P[mirror])
        # 확장
        while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
            P[i] += 1
        # 경계 갱신
        if i + P[i] > right:
            center = i
            right = i + P[i]

    # 최대 반경 위치 도출
    max_len = 0
    center_index = 0
    for i in range(1, n - 1):
        if P[i] > max_len:
            max_len = P[i]
            center_index = i

    start = (center_index - max_len) // 2  # 원본 인덱스 역투영
    return s[start:start + max_len]

def longest_palindromic_substring_center_expand(s: str) -> str:
    """
    기준선 비교용 중심 확장 O(n^2) 구현
    """
    if not isinstance(s, str):
        raise TypeError("input must be str")
    n = len(s)
    if n < 2:
        return s

    def expand(l: int, r: int) -> Tuple[int, int]:
        while l >= 0 and r < n and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r  # [l+1, r)

    best = (0, 1)
    for c in range(n):
        l1, r1 = expand(c, c)       # 홀수
        l2, r2 = expand(c, c + 1)   # 짝수
        if r1 - l1 > best[1] - best[0]:
            best = (l1, r1)
        if r2 - l2 > best[1] - best[0]:
            best = (l2, r2)
    return s[best[0]:best[1]]

if __name__ == "__main__":
    tests = ["babad", "cbbd", "a", "ac", "", "abacdfgdcaba"]
    for t in tests:
        m = longest_palindromic_substring_manacher(t)
        c = longest_palindromic_substring_center_expand(t)
        print(f"{t!r} -> Manacher: {m!r}, Center: {c!r}")
        assert len(m) == len(c)  # 최장 길이는 동일해야 함

운영 조건에서 놓치기 쉬운 부분

구분자와 센티넬은 입력에 등장하지 않는 문자로 선택하거나 사전 검사로 충돌을 막아야 한다. 바이너리 데이터를 다룰 때는 바이트 수준의 특별 값을 예약할 필요가 있다.

코드 포인트 단위 비교는 결합 문자나 이모지에서 시각적인 대칭과 다를 수 있다. 필요한 경우 NFC 정규화와 그라페메 단위 토큰화를 적용하고, 처리 후 원문 인덱스로 돌아가기 위한 매핑 테이블을 유지한다. regex \X 또는 전용 라이브러리인 grapheme, icu로 분해한 리스트를 처리한 뒤 조인하는 전략도 적용할 수 있다.

매우 긴 입력에서는 P를 array('I') 등에 저장해 메모리를 줄일 수 있다. C 확장(PyPy, Cython)은 추가 성능 향상 수단이 될 수 있다.

전통적인 Manacher는 오프라인 일괄 처리 구조다. 온라인 요구에는 슬라이딩 윈도 기반 근사 해법이나 프리픽스 확장으로 부분 결과를 제공할 수 있지만, LPS의 전역 최적성을 보장하기는 어렵다.