Manacher's Algorithm

일반적으로 문자열 속에서 팰린드롬(회문)을 찾는 알고리즘은 다음과 같이 O(n²)의 시간복잡도를 가지고 있습니다.

#include <stdio.h>
#include <string.h>
#define NMAX 35
 
int len, cnt;
char inp[NMAX];
 
bool check(int l, int r) {
    while(l<r) {
        if(inp[l++] != inp[r--]) return 0;
    }
 
    return 1;
}
 
int main() {
    scanf("%s", inp);
    len = strlen(inp);
    
    for(int i=0;i<len;i++) {
        for(int j=0;j<len;j++) {
            if(check(i, j)) cnt++;
        }
    }
    
    printf("%d", cnt);
}

하지만 Manacher의 알고리즘을 활용하면 O(n)으로 문자열 속 팰린드롬을 구할 수 있습니다.

Manacher 알고리즘은 팰린드롬의 특징인 대칭성을 이용한 알고리즘으로, 이미 구한 팰린드롬을 활용해 중복 계산 없이 팰린드롬을 구하는 알고리즘입니다. Manacher 알고리즘의 작동 과정을 하나씩 살펴봅시다.

 

Manacher 알고리즘은 문자열의 길이와 동일한 배열 m을 활용해 팰린드롬을 구합니다. m[i]는 i번째 문자를 중심으로 하는 가장 긴 팰린드롬의 반지름을 기록합니다. 예를 들어 "tabacdcaba" 문자열로 m을 만들어보면 다음과 같습니다.

 

	S[0]	S[1]	S[2]	S[3]	S[4]	S[5]	S[6]	S[7]	S[8]	S[9]
S	t	a	b	a	c	d	c	a	b	a
M	0	0	1	0	0	4	0	0	1	0

 

b의 경우, 반지름의 길이가 1이고 자신을 중심으로 하는 "aba" 팰린드롬이 있기 때문에 m에는 1이 저장됩니다. 동일하게 d의 경우 "abacdcaba" 팰린드롬이 있기에 반지름의 길이인 4가 저장됩니다. 이렇게 반지름을 저장하면 이전의 반지름을 참고해서 빠르게 팰린드롬을 구할 수 있습니다. 그렇다면 이전의 반지름의 길이를 어떻게 활용할 수 있을까요?

 

바로 팰린드롬의 대칭성을 활용하면 됩니다. 모든 팰린드롬은 대칭성을 가지고 있습니다. 따라서, 어떤 문자가 하나의 큰 팰린드롬에 속해있다면 반대편에도 대칭되는 동일한 문자가 있으며, 팰린드롬 안에서 만큼은 동일한 문자열 구조를 가지고 있다는 걸 알 수 있습니다. 예를 들어 S[8]의 b를 봅시다. b는 "abacdcaba"라는 큰 팰린드롬 안에 속해 있습니다. 따라서 b는 S[2]에 대칭되는 b가 있습니다. 또한, S[2]의 b는 S[1:3]까지의 팰린드롬을 가지고 있으며 S[8]도 마찬가지로 S[7:9]까지 팰린드롬을 가지고 있습니다. 이는 S[2]와 S[8]이 하나의 팰린드롬에서 대칭되는 대칭점이기 때문에 나타나는 현상입니다.

 

	S[0]	S[1]	S[2]	S[3]	S[4]	S[5]	S[6]	S[7]	S[8]	S[9]
S	t	a	b	a	c	d	c	a	b	a

 

따라서 우리는 S[8]을 확인할 때, 대칭점인 S[2]를 보고 팰린드롬인지 확인하는 범위를 줄일 수 있습니다. S[2]가 가지고 있는 팰린드롬 중 S[2]와 S[8]이 함께 속한 팰린드롬의 크기만큼은 확인할 필요 없기에 그 이후부터 팰린드롬인지 확인하면 됩니다.

 

지금까지의 알고리즘을 소스코드로 변환하면 다음과 같습니다.

 

for(int i=0;S[i]!='\0';i++) {
    // r: 현재 가장 오른쪽에 위치한 팰린드롬의 반지름(마지막 인덱스)
    // p: 현재 가장 오른쪽에 위치한 팰린드롬의 중심 인덱스
 
    // m[p - (i-p)]: i의 대칭점 찾기 / r-i: 자신이 속한 팰린드롬까지의 길이
    // >> 자신이 속한 팰린드롬 안에서 대칭점이 가진 팰린드롬의 반지름 구하기
    if(i < r) m[i] = std::min(m[p - (i-p)], r-i);
 
    // 현재 팰린드롬에 속하지 않았다면 0부터 탐색
    else m[i] = 0;
 
    // m[i]의 값을 누적하면서 팰린드롬의 반지름 구하기
    while(i-m[i]-1>=0 and i+m[i]+1<len and S[i-m[i]-1] == S[i+m[i]+1]) m[i]++;
 
    // 현재 만들어진 팰린드롬과 이전의 최우측 팰린드롬 비교
    if(r < i+m[i]) {
        r = i+m[i];
        p = i;
    }
}

 

이렇게 r과 p를 사용해서 현재 찾은 팰린드롬 중 가장 오른쪽 팰린드롬이 i를 포함하고 있는지 여부를 구합니다. 만약 i가 포함되어 있다면  p를 사용해 i의 대칭점인 p - (i-p)을 찾고, 대칭점이 가진 팰린드롬을 찾아서 탐색의 시작점을 설정합니다. 그 후, while문을 활용해 i를 중심으로 가질 수 있는 팰린드롬의 최대 반지름을 구한 다음, 현재 팰린드롬이 가장 오른쪽에 있는지 확인하면 됩니다.

 

위 알고리즘의 시간복잡도를 분석해보면, m[i]의 초깃값이 시간복잡도에 영향을 미치고 있음을 볼 수 있습니다. 초깃값을 어떻게 설정하느냐에 따라 while문의 실행 횟수가 줄어들기 때문입니다. 그렇다면 m[i]가 가질 수 있는 초깃값을 하나씩 살펴보면서 나올 수 있는 경우의 수를 파악해봅시다.

 

(1) m[i] = m[p - (i-p)]인 경우
m[i]의 초깃값이 대칭점의 반지름이라면 while문을 실행하지 않습니다.
초깃값이 대칭점의 반지름이라는 건 m[i]를 중심으로 한 팰린드롬은 현재 m[i]를 포함한 팰린드롬 안에 있다는 의미이며, 팰린드롬은 대칭이기 때문에 m[i]의 값은 m[p - (i-p)]보다 커질 수 없습니다. 따라서 while문은 실행되지 않습니다.

 

(2) m[i] = r-i인 경우 / m[i] = 0인 경우
이 경우, while문이 실행된 이후에 r = i+m[i]가 항상 실행될 것입니다. 새롭게 만들어진 팰린드롬은 항상 가장 오른쪽에 위치하기 때문입니다. 또한, while문에서는 m[i]의 값이 1씩 증가하며 절대 줄어들지 않습니다. 따라서 while문으로 인해 바뀌는 r이 최대 문자열의 길이(len)까지 변하기 때문에 시간 복잡도는 O(n)이 되며, O(n)은 전체 알고리즘의 시간 복잡도가 됩니다.

 

 

Manacher의 알고리즘을 사용하면 팰린드롬을 빠르게 구할 수 있지만, 알고리즘 특성 상 길이가 짝수인 팰린드롬은 구할 수 없습니다. 길이가 짝수인 팰린드롬은 중심이 되는 문자가 없기 때문입니다. 하지만 문자 사이사이에 특정 문자(Ex. '@')를 넣어주면 길이가 짝수인 팰린드롬까지 구할 수 있습니다. 예를 들어 "abba" 문자열을 Manacher 알고리즘으로 판단하기 위해서는 "a@b@b@a"로 변환해야 합니다. 이렇게 변환하면 '@'가 기준이 될 수 있기 때문에 Manacher 알고리즘을 사용할 수 있습니다.

 

 

 

지금까지 팰린드롬을 빠르게 구할 수 있는 Manacher 알고리즘을 알아보았습니다. 아래 사이트를 방문하면 더 자세한 내용을 볼 수 있습니다.

 

(1) 알고스팟 : https://algospot.com/wiki/read/Manacher's_algorithm

algospot.com :: Manacher's algorithm

(2) 위키피디아(최장 부분 팰린드롬) : https://en.wikipedia.org/wiki/Longest_palindromic_substring

Longest palindromic substring - Wikipedia