💡 가장 빠르게 팰린드롬을 찾는 알고리즘, Manacher’s Algorithm

 

💡 가장 빠르게 팰린드롬을 찾는 알고리즘, Manacher’s Algorithm

팰린드롬(Palindrome)은 앞에서 읽든 뒤에서 읽든 같은 문자열을 말합니다.
예: "abba", "racecar", "a" 등.

많은 문자열 문제 중 "가장 긴 팰린드롬 부분 문자열"을 찾는 문제는 매우 유명합니다.
일반적으로는 다이내믹 프로그래밍(DP)을 활용해서 O(n²) 시간에 해결하지만,
O(n) 시간에 해결 가능한 아주 특별한 알고리즘이 있습니다.

 

바로 오늘 소개할 Manacher’s Algorithm (마나처 알고리즘) 입니다.

---

🧩 문제 정의

문자열 s가 주어졌을 때,
그 안에 포함된 가장 긴 팰린드롬 부분 문자열을 찾아라.

예시:

Input:  "babad"
Output: "bab" (또는 "aba")

---

⏱️ 시간복잡도 비교

알고리즘 시간 복잡도

완전탐색	O(n³)
다이내믹 프로그래밍	O(n²)
Manacher	O(n)

---

⚙️ 알고리즘 아이디어

1. 중간에 #을 삽입해 짝/홀 팰린드롬을 통일

• 예: "abba" → ^#a#b#b#a#$
• 시작(^)과 끝($)에 특수문자를 넣어 인덱스 오류 방지

2. P[i]: i를 중심으로 하는 팰린드롬의 반지름 길이

• 팰린드롬의 길이는 2*P[i] + 1

3. center, right 유지

• center: 현재 가장 멀리까지 뻗은 팰린드롬의 중심
• right: 그 팰린드롬의 오른쪽 경계

4. 대칭 속성 이용해 계산 최적화

• mirror = 2*center - i
• P[i] = min(P[mirror], right - i)로 예측값 설정

5. 확장 검사

• T[i + P[i] + 1] == T[i - P[i] - 1]인 동안 계속 확장

---

🧑‍💻 파이썬 코드

def preprocess(s):
    return "^#" + "#".join(s) + "#$"

def longest_palindrome(s):
    T = preprocess(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 + P[i] + 1] == T[i - P[i] - 1]:
            P[i] += 1

        if i + P[i] > right:
            center = i
            right = i + P[i]

    max_len = max(P)
    center_index = P.index(max_len)
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

---

🧩 1. 전처리 함수

def preprocess(s):
    return "^#" + "#".join(s) + "#$"

• 문자열 s를 #로 구분해줍니다: "abba" → ^#a#b#b#a#$
• ^, $는 경계 문자로서 인덱스 오류 방지를 위해 넣습니다.
• 모든 팰린드롬을 홀수 길이로 변환해 짝수/홀수 구분 없이 처리 가능하게 만듭니다.

---

📌 예시

s = "abba"
T = "^#a#b#b#a#$"

• 길이: 11
• 이제 T의 각 위치는 실제 문자 또는 문자 사이를 의미합니다.

---

🧮 2. 초기 변수 설정

n = len(T)
P = [0] * n        # 각 위치에서의 팰린드롬 "반지름 길이" 저장
center = right = 0 # 현재까지 발견된 가장 오른쪽 끝나는 팰린드롬 정보

• P[i]는 T[i]를 중심으로 확장 가능한 반지름 길이 (자기 자신 제외)
• center: 현재까지 가장 멀리 뻗은 팰린드롬의 중심
• right: 그 팰린드롬의 오른쪽 경계 인덱스

---

🔄 3. 팰린드롬 탐색 루프

for i in range(1, n - 1):  # 경계 문자 ^, $ 제외

---

3-1. 대칭점 계산 및 초기 반지름 설정

mirror = 2 * center - i
if i < right:
    P[i] = min(right - i, P[mirror])

• mirror는 i에 대해 center 기준으로 대칭인 위치
• P[i]는 mirror의 값을 참조해서 초기화하되,
  경계를 넘어가지 않도록 right - i 제한을 둠

📌 핵심 아이디어:

이미 팰린드롬임이 확인된 영역 안에 있다면, mirror 정보를 활용해 최소한의 확장 시도만 하면 된다.

---

3-2. 실제 팰린드롬 확장 시도

while T[i + P[i] + 1] == T[i - P[i] - 1]:
    P[i] += 1

• 현재 중심 i에서 팰린드롬이 더 확장될 수 있는지 계속 확인
• 문자가 대칭이면 계속 반지름 증가

---

3-3. 경계 갱신

if i + P[i] > right:
    center = i
    right = i + P[i]

• 새로 확장된 팰린드롬이 이전 경계를 넘었다면,
  이 팰린드롬이 가장 긴 오른쪽 팰린드롬이 되므로 center와 right 갱신

---

📍 4. 최장 팰린드롬 찾기

max_len = max(P)
center_index = P.index(max_len)
start = (center_index - max_len) // 2
return s[start:start + max_len]

• P 배열에서 가장 큰 값(가장 긴 반지름)을 찾아 팰린드롬 중심 인덱스 계산
• 전처리 문자열의 인덱스를 원래 문자열 인덱스로 되돌릴 때 // 2 필요
• 원본 문자열 s에서 시작 위치부터 길이만큼 잘라 반환

---

🧪 예제 디버깅 (입력: "abba")

전처리 문자열: ^ # a # b # b # a # $
P 값 (반지름): [0,0,1,0,1,4,1,0,1,0,0]
→ P[5] = 4 → "abba"의 길이 4

---

📌 전체 요약

단계 설명

전처리	문자열에 # 삽입해 모든 팰린드롬을 홀수 길이로 통일
P[i]	각 중심마다 팰린드롬 반지름 저장
mirror	대칭 위치의 정보 활용해 중복 계산 최소화
확장	T[i ± P[i] + 1] 비교로 양옆 확장
결과	최대 반지름과 중심을 이용해 원래 문자열에서 자름

---

🧠 기억할 키포인트

• 팰린드롬 문제에만 특화된 고성능 알고리즘
• 짝수/홀수 구분 없이 처리하기 위한 전처리가 핵심
• 중심과 대칭 정보를 활용한 빠른 확장

---

📌 핵심 직관

✅ 팰린드롬은 대칭이다!

• 예를 들어 T = "^#a#b#b#a#$" 에서
  중심이 5(b), 반지름이 4인 팰린드롬은 → "abba"를 의미

  인덱스:     0 1 2 3 4 5 6 7 8 9 10
  문자:       ^ # a # b # b # a # $
                ↖↖↖center↗↗↗
                   ↖↖right

• 이제 우리가 i = 6을 검사할 때, mirror = 2*5 - 6 = 4
• P[4] = 1이라면, 대칭 위치의 팰린드롬 정보를 바탕으로 P[6]은 최소한 1 이상 확장될 수 있다는 걸 예상할 수 있음

---

🎯 왜 이게 중요한가?

이전 중심 center의 팰린드롬이 끝나는 범위는 [center - P[center], center + P[center]] = [left, right]입니다.

• 이 범위 안에 있는 i는 mirror(i)에 대한 정보만으로 팰린드롬 길이를 유추할 수 있어요.
• 따라서 불필요한 문자 비교 없이 P[i] = min(P[mirror], right - i)로 초기화하고,
  그 이상만 실제 비교해서 확인하면 됩니다.

---

🧠 예시 시각화

전처리된 문자열: "^#a#b#b#a#$"

(문자열 "abba"의 전처리 결과)

탐색 흐름 (일부 생략):

1. i = 5, center = 5, right = 9
   → 팰린드롬 "abba" 찾음 → P[5] = 4, center/right 갱신
2. i = 6, mirror = 4
   • P[4] = 1
   • right - i = 9 - 6 = 3
   • P[6] = min(1, 3) = 1 로 초기화
   • 그 이후 추가 확장 시도 (필요할 경우만)
3. i = 7, mirror = 3
   • P[3] = 0
   • right - i = 2
   • P[7] = 0 로 초기화 → 확장 시도

---

📉 얼마나 중복 계산을 줄일 수 있나?

❌ 비교 기반 알고리즘 (e.g., 중심 확장법)

• 모든 문자 중심으로 좌우 확장 → 최대 O(n²) 비교 발생

✅ Manacher

• 이미 검사된 영역은 mirror로 빠르게 유추
• 확장이 필요한 새 영역만 직접 문자 비교
• 전체 문자열을 한 번만 순회 → O(n)

---

🧪 비유로 이해해보기

거울 앞에서 팰린드롬을 검사하는 장면을 상상해보세요.

• 한쪽 팰린드롬 구조를 알면,
• 거울 반대편 구조는 그대로 복사될 거라고 "예상"할 수 있어요.
• 이때, 거울에서 잘 안 보이는 범위만 직접 확인하면 되는 거예요.

---

📝 정리

개념 역할

center	현재까지 가장 멀리까지 뻗은 팰린드롬의 중심
right	그 팰린드롬의 오른쪽 끝 인덱스
mirror	i의 대칭 인덱스, 2*center - i
최적화 포인트	P[i] = min(P[mirror], right - i) 로 빠른 초기화
중복 제거 방법	이미 팰린드롬임이 확정된 영역은 재검사하지 않음

 

 

---

📌 요약

항목 내용

목적	가장 긴 팰린드롬 부분 문자열 찾기
전략	중심 확장 + 대칭 이용
시간 복잡도	O(n)
처리 가능한 팰린드롬 종류	홀수, 짝수 모두 (중간에 # 삽입으로 통일)
단점	구현이 복잡하고 디버깅이 어려움

---

✅ 마무리

Manacher’s Algorithm은 알고리즘 대회나 코딩 테스트에서
시간 성능이 핵심인 팰린드롬 문제를 푸는 최고의 무기입니다.

물론 처음엔 복잡해 보일 수 있지만, 원리를 한 번 이해하고 나면
문자열 알고리즘의 아름다움을 느낄 수 있는 멋진 도구가 됩니다.