PS 문자열 알고리즘 - 4. Manacher 알고리즘

kdy40929 2025. 8. 9. 15:48

이번에 글을 적어볼 알고리즘은 매내처 알고리즘이다. 이 역시 바로 본론으로 들어가자면, 매내처 알고리즘은 어떤 문자열 $S$가 주어졌을 때, $S$의 부분 문자열 (앞뒤에서 0개 이상의 문자를 떼어내 만들 수 있는 문자열) 중 팰린드롬인 것을 빠르게 탐색하는 알고리즘이다. 그리고 실제 구현은 Z 알고리즘과 비슷하게 이루어진다.

Manacher 알고리즘은 부분 문자열 중 팰린드롬을 팰린드롬의 중심을 기준으로 탐색한다. 예시를 들어서 설명하자면, 팰린드롬 abcba의 중심은 c이고, abcba가 팰린드롬임을 알면 중심을 기준으로 대칭인 c, bcb가 팰린드롬이라는 사실을 이용할 수 있는 것이다. 이때 위 팰린드롬의 반경은 $2$이다. 왜냐하면 c를 중심으로 오른쪽으로 두 칸, 왼쪽으로 두 칸이 서로 대칭이라서 팰린드롬을 이루기 때문이다.

매내처 알고리즘은 결국 $i$번째 인덱스의 문자를 중심으로 할 때 최대 팰린드롬 반경 $A[i]$를 빠르게 구하는 알고리즘이다.

A  A  B  A  C  D  C  A  B  A  C  B
   |-----------|--------|--|
              ctr       |  r
                        i

위와 같은 문자열을 생각하고, D를 중심으로 하는 팰린드롬의 반경이 4인 상황을 고려하자. 우리는 $i = 8$ 인덱스를 살피고 있다. 여기서 팰린드롬 반경을 어떻게 빠르게 구할 수 있을까? 그 원리는 Z 알고리즘과 비슷하다. 우리는 ctr을 중심으로 서로 문자열이 대칭을 이루고 있음을 알고 있으므로 2*ctr - i에 해당하는, 즉 2번 인덱스의 B를 이용해서 팰린드롬 반경을 빠르게 구할 수 있는 것이다.

하지만 이 상황에서도 조심해야 될 부분이 있다. 바로 팰린드롬 반경이 $r$ 범위를 벗어나는 경우이다. 위 상황에서도 $A[2] = 1$인 반면, $A[8]$은 $A[2]$를 이용해서 빠르게 계산하려고 함에도 반경 $2$만 되려고 해도 $r$ 범위를 넘어서게 된다. 이럴 때에는 Z 알고리즘처럼 직접 문자를 비교해서 $A[i]$를 채워야 한다.

그리고 $r$의 범위는 최대한 뒤쪽까지 포함하고 있어야 최적화가 가능하므로 $r$의 값을 갱신해주어야 한다. 위의 상황에서 일어난 갱신을 그림으로 표현하면 아래와 같다. 원래의 $i$ 위치에 $ctr$이 배정되었고, $r$은 $i+A[i]$ 위치가 된다.

A  A  B  A  C  D  C  A  B  A  C  B
                  |-----|-----|
                        |     r
                       ctr

따라서,

1. $r$의 값을 이용해서 $A[i]$ 구하기
2. $A[i]$의 범위가 $r$을 초과할 경우 직접 비교하기
3. $r$이 더 뒤로 이동할 수 있다면 $ctr, r$ 갱신하기

위 3가지를 이용하면 매내처 알고리즘을 구현할 수 있다. 실제로 구현도 원리도 Z 알고리즘과 크게 다르지 않다.

따라서 이를 Python으로 구현하면 아래와 같다.

def manacher(s):
    n = len(s)
    r, ctr = 0, 0
    arr = [0 for _ in range(n)]
    for i in range(n):
        if i <= r:
            arr[i] = min(arr[2*ctr-i], r-i)
        while i-arr[i] >= 1 and i+arr[i] < n-1 and s[i-arr[i]-1] == s[i+arr[i]+1]:
            arr[i] += 1
        if r < i+arr[i]:
            r, ctr = i+arr[i], i
    return arr

그런데...! 여기서 아주 중요한 이슈가 하나 있다. 바로 매내처 알고리즘은 홀수 길이의 팰린드롬만 찾을 수 있다는 것이다. 이유는 간단하다. 팰린드롬의 중심을 우리는 "문자"로 잡았기 때문이다. 짝수 길이의 팰린드롬, 이를테면 abba는 중심이 문자가 아니다. 두 b 사이 지점이 중심이다.

하지만 우리가 짝수 길이의 팰린드롬을 찾는 알고리즘을 다시 고안하는 것은 너무 귀찮기 때문에 이웃한 두 문자 사이 지점 자체를 다시 문자로 만드는 일종의 trick을 사용할 것이다. 바로 *와 같은 문자를 끼워넣는 것이다.

즉, 문자열 abbac가 주어졌다면 이를 *a*b*b*a*c* 로 바꿀 것이고, 그러면 abba라는 팰린드롬은 *a*b*b*a*의 형태가 되어 b와 b 사이의 *을 중심으로 하는 홀수 길이의 팰린드롬으로 바뀌게 되는 것이다. 이때 유의해야 할 점은 끼워넣는 문자는 원래 문자열에서 사용되지 않는 문자여야 한다는 점이다. 따라서 보통은 입력받은 문자열에 포함되어 있지 않은 특수문자를 사용하는 것이 일반적이지만, 어떤 문자를 사용할지는 개인의 선택이다.

따라서 실제로 매내처 알고리즘을 사용할 때에는 아래 코드와 같이 사용하게 된다.

def manacher(s):
    n = len(s)
    r, ctr = 0, 0
    arr = [0 for _ in range(n)]
    for i in range(n):
        if i <= r:
            arr[i] = min(arr[2*ctr-i], r-i)
        while i-arr[i] >= 1 and i+arr[i] < n-1 and s[i-arr[i]-1] == s[i+arr[i]+1]:
            arr[i] += 1
        if r < i+arr[i]:
            r, ctr = i+arr[i], i
    return arr

inp = input().rstrip()
s = '*' + '*'.join(inp) + '*'
manacher(s)

하지만 짝수 길이의 팰린드롬을 처리하다 보면 또 새로운 문제점이 생긴다. 바로 array에 저장되는 팰린드롬 반경의 값이 원래 정의에서의 값과 달라지는 것이다.

하지만 이게 오히려 이점을 주기도 한다. 왜냐하면 이때 array에 저장되는 값은 바로 그 지점을 중심으로 하는 팰린드롬의 최대 길이가 되기 때문이다. 예시를 들어 문자열 abaa를 살펴본다면, *a*b*a*a*을 이용해 매내처 알고리즘을 돌리면 얻는 배열은 $[0, 1, 0, 3, 0, 1, 2, 1, 0]$이다. b를 중심으로 하는 팰린드롬 반경은 *을 추가한 문자열에서 3이고, 그리고 이 값은 원본 문자열에서 b를 중심으로 하는 팰린드롬의 최대 길이와 정확히 일치한다. 또한, 뒤쪽의 a 2개 사이의 *을 중심으로 하는 팰린드롬 반경은 2이고, 이 역시 원본 문자열에서 두 a 사이를 중심으로 하는 팰린드롬의 최대 길이와 정확히 일치한다.

다음으로 살펴볼 것은 매내처 알고리즘의 시간복잡도이다. 앞서 Z 알고리즘과 구현 형태가 비슷하기 때문에 Z 알고리즘과 비슷한 방식으로 시간복잡도 분석을 진행할 수 있다.

while문 내에서 arr[i] += 1을 1회 진행할 때마다 그 이후 $r$은 최소 1만큼 증가한다는 사실을 쉽게 알 수 있는데, $r$의 범위가 $S$의 길이 이하로 제한되기 때문에 시간복잡도가 $O(N)$이 된다. 잘 이해가 안 된다면 이전 블로그에서 다룬 Z 알고리즘의 시간복잡도 분석을 읽어보면 도움이 될 것이다.

이를 이용하면 매내처 알고리즘으로 팰린드롬 관련 문자열 문제를 쉽게 해결할 수 있는 경우가 많다. 아래에서는 여러 백준 문제 예시를 통해 살펴보자.

<BOJ 13275 가장 긴 팰린드롬 부분 문자열> https://www.acmicpc.net/problem/13275

고민할 것도 없다. 위에서 설명한 그대로이므로 max(arr)를 출력하면 끝나는 문제가 되겠다.

코드는 아래와 같다

def manacher(s):
    n = len(s)
    r, ctr = 0, 0
    arr = [0 for _ in range(n)]
    for i in range(n):
        if i <= r:
            arr[i] = min(arr[2*ctr-i], r-i)
        while i-arr[i] >= 1 and i+arr[i] < n-1 and s[i-arr[i]-1] == s[i+arr[i]+1]:
            arr[i] += 1
        if r < i+arr[i]:
            r, ctr = i+arr[i], i
    return arr

inp = input().rstrip()
s = '*' + '*'.join(inp) + '*'
print(max(manacher(s)))

<BOJ 16163 #15164번_제보> https://www.acmicpc.net/problem/16163

이 문제는 부분 문자열 중 팰린드롬의 개수를 세는 것이다. 어떤 문자를 중심으로 하는 팰린드롬의 최대 길이가 $x$이면 이 문자를 중심으로 하는 팰린드롬의 개수는 $\left \lfloor{\frac{x+1}{2}}\right \rfloor$ 이다.

따라서 이를 이용하여 정답을 구하는 코드를 짜면 아래와 같다.

def manacher(s):
    n = len(s)
    r, ctr = 0, 0
    arr = [0 for _ in range(n)]
    for i in range(n):
        if i <= r:
            arr[i] = min(arr[2*ctr-i], r-i)
        while i-arr[i] >= 1 and i+arr[i] < n-1 and s[i-arr[i]-1] == s[i+arr[i]+1]:
            arr[i] += 1
        if r < i+arr[i]:
            r, ctr = i+arr[i], i
    return arr

inp = input().rstrip()
s = '*' + '*'.join(inp) + '*'
ans = 0
arr = manacher(s)
for i in range(len(arr)):
    ans += (arr[i]+1)//2
print(ans)

<BOJ 30400 팰린드롬 제거> https://www.acmicpc.net/problem/30400

이번에는 조금 더 난이도 있는 문제를 풀어보자. 이제는 매내처 알고리즘을 활용한 문제들이다. 부분 문자열 중 길이 $M$ 이상인 팰린드롬이 남아 있지 않도록 최소한의 문자를 파괴해야 하는 문제이다.

먼저, 매내처를 이용해서 각 문자를 중심으로 하는 팰린드롬의 최대 길이를 찾을 수 있고, 이 중 길이가 $M$ 이상인 것만 남기는 것까지는 어렵지 않게 할 수 있다. 그 다음은 어떤 전략을 사용해야 할까? 여기서 아래와 같은 2가지 관찰을 할 수 있다.

관찰 1. 중심이 같은 길이 $M$ 이상인 팰린드롬에 대해서는 가장 짧은 것만 보면 충분하다.

이를 예시를 들어서 설명하면 아래와 같다. $M = 3$이라고 해보자.

.. A B C D C B A ..
         |
       |---|
     |-------|
   |-----------|
        ...

D를 중심으로 하는 팰린드롬이 가장 짧은 것부터 굉장히 많은데, 이 중에서 길이가 3보다 작은 D는 제거하지 않아도 된다. 그 다음인 CDC는 길이가 3이므로 반드시 제거해야 하는데, CDC를 제거하면 자동으로 이보다 더 긴 팰린드롬인 BCDCB, ABCDCBA ...은 무조건 지워진다. 따라서 각 팰린드롬의 중심마다 제거해야 하는 팰린드롬의 수를 최대 1개로 제한할 수 있다.

관찰 2. (왼쪽부터 팰린드롬을 제거할 때) 제거해야 하는 팰린드롬이 생긴다면 팰린드롬의 가장 오른쪽 문자를 제거하는 전략이 유효하다. 이 그리디 전략은 꽤나 자명하다. 가장 오른쪽 문자가 아닌 문자를 제거할 때보다 같거나 더 많은 팰린드롬을 한꺼번에 제거할 수 있기 때문이다.

이 두 가지 관찰을 바탕으로 최소한의 제거 횟수로 길이 $M$ 이상의 팰린드롬을 제거하는 전략을 세워 보면, 관찰 1을 바탕으로 각 위치를 중심으로 하는 제거해야 하는 팰린드롬을 최대 1개 선정한다. 그리고 이 팰린드롬들을 왼쪽에 위치한 것부터 보면서 아직 제거되지 않은 것이 발견될 때마다 가장 오른쪽 문자를 제거하면 된다.

이를 구현한 코드가 아래와 같다.

import sys
input = sys.stdin.readline
def manacher(s):
    n = len(s)
    r, ctr = 0, 0
    arr = [0 for _ in range(n)]
    for i in range(n):
        if i <= r:
            arr[i] = min(arr[2*ctr-i], r-i)
        while i-arr[i] >= 1 and i+arr[i] < n-1 and s[i-arr[i]-1] == s[i+arr[i]+1]:
            arr[i] += 1
        if r < i+arr[i]:
            r, ctr = i+arr[i], i
    return arr

n, m = map(int, input().split())
inp = input().rstrip()
s = '*' + '*'.join(inp) + '*'
arr = manacher(s)
lst = []
for i in range(2*n+1):
    if arr[i] >= m:
        lst.append(((i-m)//2, (m+i-1)//2))
ans, last = 0, -1
for x, y in lst:
    if last < x:
        last = y
        ans += 1
print(ans)

원본 문자열에서의 인덱스와 *을 추가한 문자열에서 인덱스가 약간 상이하므로 //2 처리를 할 때 꼼꼼한 계산이 필요하다.

여기까지 매내처 알고리즘을 공부하였고, 이에 관련된 문제도 3문항 풀어보았다. 다음에는 해싱 (라빈 카프) 알고리즘을 소개할 예정이다.

'PS' 카테고리의 다른 글

PS 문자열 알고리즘 - 6. 접미사 배열과 lcp 배열 (0)	2025.08.12
PS 문자열 알고리즘 - 5. 라빈 카프 알고리즘 (해싱) (2)	2025.08.10
PS 문자열 알고리즘 - 3. Z 알고리즘 (3)	2025.08.08
PS 문자열 알고리즘 - 2. KMP 응용 (4)	2025.08.04
PS 문자열 알고리즘 - 1. KMP 알고리즘 (3)	2025.08.03

현재글PS 문자열 알고리즘 - 4. Manacher 알고리즘

PS하는 kdy

PS를 취미로 하고 있는 고등학생의 블로그입니다.

1786, lcp배열, 알고리즘, 문자열, 대회후기, 2025koi, 접미사배열, 백준, rabin karp, suffix array, KOI MOCK, string, 프로그래밍, ps, KMP, BOJ, 매내처, 정올, 솔브닥, KOI,

Today :
Yesterday :

PS하는 kdy