Manacher 알고리즘(Manacher's Algorithm)

---

목차

1. Manacher 알고리즘(Manacher's Algorithm)란?

2. manacher 알고리즘 동작 원리

3. manacher 알고리즘 접목

4. 관련 문제

---

1. Manacher 알고리즘(Manacher's Algorithm)란?

이번 포스팅에서는 Manacher 알고리즘(Manacher's Algorithm)에 대해 알아보고자 한다.

우선 manacher 알고리즘이 언제 쓰이고, 왜 쓰이는지 알아보자.

앞서 필자는 부분 문자열의 팰린드롬 판별 알고리즘에 대해 설명한 적이 있다.

http://www.crocus.co.kr/1001

위의 알고리즘은 O(n^2)이라는 시간 복잡도를 가지고 있어 n = 10000이 된다면 시간 복잡도가 1억이 된다.

따라서 10000이상의 길이를 가진 문자열의 부분 문자열에 대해서 팰린드롬 판단 빠르게 해줄 수 없다.

이를 위해 우리는 문자열의 부분 문자열이 팰린드롬인지 O(n)에 판단하는 manacher 알고리즘을 알아보고자 한다.

manacher 알고리즘의 시간 복잡도 :: O(n)

2. manacher 알고리즘 동작 원리

manacher 알고리즘을 이용하여 우선 문자열 S에 대한 배열 A를 구할 수 있다.

이때 배열 A는 다음과 같이 정의된다.

A배열 i번째 원소 A[i]는 i번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기를 의미한다.

예를들어 bananac에서 붉은색 a의 A[4]는 최대 반지름인 2가 된다.

즉, 부분 문자열 S의 4 - A[4]에서 4 + A[4]까지는 팰린드롬이며, 4 - A[4] - 1에서 4 + A[4] + 1까지는 팰린드롬이 아니다.

(anana는 팰린드롬이지만, bananac는 팰린드롬이 아니다.)

이를 일반화 하면 어떤 문자열 S에서 A[i]가 존재한다면, 

i - A[i]에서 i + A[i]까지는 팰린드롬이고, i - A[i] - 1에서 i + A[i] + 1까지는 팰린드롬이  아니라는 것이다.

이 과정을 이용하여 bananac라는 문자열에 대한 배열 A를 알아보자.

S	b	a	n	a	n	a	c
A	0	0	1	2	1	0	0

manacher 알고리즘 동작 원리는 다음과 같다.

1. i는 1부터 N(문자열의 길이)까지 진행된다.

2. j < i인 모든 j에 대해 r=max(j + A[j])이라 하고, 또한 그러한 j를 p라 하자. 즉, r=p + A[p]

3. i와 r의 대소 관계에 따라 A[i]의 초기값이 결정된다.

  1. i > r이라면, A[i]의 초기값은 0이다.

  2. i ≤ r이라면, i는 p를 중심으로 한 회문에 속한다. 따라서 그 회문에서 i의 대칭점을 i′라 하자. 즉, i′=2p - i가 된다.

     그리고 A[i]의 초기값은 min(r - i, A[i′])이다. (즉, r은 중심점 p를 기준으로 하는 p + A[p]를 의미하게 된다.)

4. A[i]의 초기값이 결정되고, S[i - A[i]]와 S[i + A[i]]가 같을 때까지 A[i]를 증가시킨다.

bananac는 위와 같이 형성됨을 알 수 있다.

각 인덱스에 대해 r이 의미해주는 것은 각 인덱스에 대해 팰린드롬이 될 수 있는 최대 범위를 말해주고 있고

p는 그러한 r이 형성되고 있는 중심점을 나타내주고 있다.

이 과정을 코드로 나타내면 다음과 같다.

void manachers(string S, int N)
{
    int r = 0, p = 0;
    for (int i = 0; i < N; i++)
    {
        if (i <= r)
            A[i] = min(A[2 * p - i], r - i);
        else
            A[i] = 0;
 
        while (i - A[i] - 1 >= 0 && i + A[i] + 1 < N && S[i - A[i] - 1] == S[i + A[i] + 1])
            A[i]++;
        
        if (r < i + A[i])
        {
            r = i + A[i];
            p = i;
        }
    }
}

이때 우리는 baaba라는 문자열이 존재 할 때 aa의 팰린드롬을 구할 수 없게 된다.

왜냐면 위의 코드로는 aab 혹은 baa같은 문자열 밖에 확인 하지 못하기 때문이다.

따라서 우리는 저러한 짝수 부분 문자열의 팰린드롬을 구하기 위해 

#b#a#a#b#a#로 문자를 치환해준다면 a#a에서 #을 이용하여 팰린드롬을 구할 수 있다.

3. manacher 알고리즘 접목

가장 대표적인 예제 문제를 하나 풀어보자.

[14444번] 가장 긴 팰린드롬 :: https://www.acmicpc.net/problem/14444

이 문제는 위의 O(n^2)의 부분 문자열의 팰린드롬 판별 알고리즘으로 해결 할 수 없다.

http://www.crocus.co.kr/1001

이제 manacher 알고리즘을 접목해보자.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
 
using namespace std;
 
const int MAXN = 100001 * 2;
 
string tmp, str;
 
int A[MAXN];
 
void manachers(string S, int N)
{
    int r = 0, p = 0;
    for (int i = 0; i < N; i++)
    {
        if (i <= r)
            A[i] = min(A[2 * p - i], r - i);
        else
            A[i] = 0;
 
        while (i - A[i] - 1 >= 0 && i + A[i] + 1 < N && S[i - A[i] - 1] == S[i + A[i] + 1])
            A[i]++;
 
        if (r < i + A[i])
        {
            r = i + A[i];
            p = i;
        }
    }
}
int main()
{
    cin >> tmp;
 
    int len = tmp.size();
 
    for (int i = 0; i < len; i++)
    {
        str += '#';
        str += tmp[i];
    }
    str += '#';
 
    manachers(str, str.size());
 
    len = str.size();
    int ans = -1;
    for (int i = 0; i < len; i++)
        ans = max(ans, A[i]);
 
    printf("%d", ans);
 
    return 0;
}

bananac를 보면

#b#a#n#a#n#a#c가 된다.

이때 #b#a#n#a#n#a#c에서 a를 기준으로 A[8]은 5가 될 것이다.

#을 추가함으로써 붉은색 a에서의 최종 팰린드롬 길이가 5가 됨도 파악 할 수 있다.(anana)

그 이유는 a를 기준으로 왼쪽에 오른쪽의 ac가 #으로 대체되기 때문이다.

4. 관련 문제

http://www.crocus.co.kr/search/manacher