매내처 알고리즘이란?

문자열에서 모든 팰린드롬(회문)을 O(N) 시간에 찾아내는 알고리즘이다. 회문에만 사용하는 알고리즘이라 사용처는 적다.

핵심 개념

• 중심을 기준으로 팰린드롬을 확장해나가는 방식을 사용한다.
• 문자열 사이에 특수문자(보통 #)를 삽입하여 홀수/짝수 길이의 팰린드롬을 동일하게 처리한다.
• 이전에 찾은 팰린드롬 정보를 활용하여 중복 계산을 피한다.

알고리즘 동작 과정

1. 원본 문자열 사이에 특수문자를 삽입하여 새로운 문자열을 만든다.예시: "abba" → "#a#b#b#a#" 이렇게 하면 짝수 길이의 팰린드롬도 홀수 길이처럼 처리할 수 있다.
2. 각 위치에서 팰린드롬의 반지름 값을 저장하는 배열 P를 만든다.예시: 문자열 "aba"에서 "#a#b#a#"로 변환 후, P[0]=0 (#), P[1]=1 (a), P[2]=0 (#), P[3]=2 (b), P[4]=0 (#) 등으로 저장된다.
3. 중심점 C와 팰린드롬의 오른쪽 끝 R을 관리하며 알고리즘을 진행한다.C는 현재까지 발견된 가장 긴 팰린드롬의 중심이다. R은 해당 팰린드롬의 가장 오른쪽 위치를 나타낸다.
4. 현재 위치 i에서 대칭점을 이용하여 P[i]의 초기값을 설정한다.대칭점은 중심 C를 기준으로 i와 대칭인 위치이다. 예시: "ababa"에서 중심이 'b'일 때, 양쪽 'a'는 서로 대칭이다.
5. 가능한 경우 팰린드롬을 확장한다.초기값 설정 후, 양쪽으로 문자를 비교하며 팰린드롬의 크기를 키운다. 예시: "#a#b#a#"에서 i=3(b)위치에서 시작하면, 양쪽의 'a'가 같으므로 P[3]=2가 된다.

시간 복잡도

전체 알고리즘의 시간 복잡도는 O(N)이다. 이는 각 위치에서 최대 한 번씩만 확장이 일어나기 때문이다.

구현 예시

def manacher(s: str) -> list:
    t = '#' + '#'.join(s) + '#'
    P = [0] * len(t)
    c = r = 0
    for i in range(len(t)):
        if i < r:
            P[i] = min(r - i, P[2 * c - i])
        while (i + P[i] + 1 < len(t) and 
               i - P[i] - 1 >= 0 and 
               t[i + P[i] + 1] == t[i - P[i] - 1]):
            P[i] += 1
        if i + P[i] > r:
            c = i
            r = i + P[i]
    return P