Manacher 알고리즘

Manacher 알고리즘

문자열의 모든 위치에서 최장 팰린드롬(회문) 길이를 O(n) 시간에 계산하는 알고리즘으로, 이전에 계산된 팰린드롬 정보를 재활용하여 중복 계산 제거

목적: 최장 팰린드롬 찾기, 선형 시간 팰린드롬 검사

특징: 선형 시간(O(n)), 중복 제거, 짝수/홀수 팰린드롬 통일 처리

전처리: 짝수/홀수 길이 팰린드롬 통일 처리 위해 구분자 삽입, "abc" → "#a#b#c#"

핵심 아이디어: 이미 계산된 팰린드롬의 대칭성 활용, 중심(center)과 오른쪽 끝(right) 추적

동작: ① 문자열 전처리 → ② 각 위치 i에서 팰린드롬 반지름 계산 → ③ i가 right 내부면 대칭 위치 정보 재활용 → ④ 확장 가능하면 확장 → ⑤ center, right 갱신

배열 P[i]: 위치 i를 중심으로 하는 최장 팰린드롬 반지름

시간 복잡도: O(n) - 각 문자는 최대 한 번만 확장 검사

공간 복잡도: O(n) - P 배열

장점: 선형 시간(O(n)), 모든 팰린드롬 찾기, 효율적

단점: 구현 복잡, 전처리 필요, 이해 어려움

적용사례: 최장 팰린드롬 부분 문자열, 팰린드롬 개수, 문자열 처리, 알고리즘 대회

비교: Manacher(O(n)/선형) vs 중심확장(O(n²)/단순) vs DP(O(n²)/공간많음)

연관: 팰린드롬, 문자열, 중심 확장, 대칭성