89. Manacher

Manacher's Algorithm은 문자열에 존재하는 팰린드롬 부분 문자열을 빠르게 찾을 수 있는 알고리즘이다. 팰린드롬(회문, Palindrome)은 전체를 뒤집었을 때 원래 상태와 같은 수열, 문자열 등을 의미하며, 팰린드롬 부분 문자열은 부분 문자열 중 팰린드롬인 것을 의미한다.

 

단어 Manacher는 이 블로그에서 소개하는 모든 용어들 중에 거의 유일하게 한국어 발음이 불분명하며, 'Ma-' 부분은 '마' 또는 '매', '-na-' 부분은 '나', '내', 또는 '니', '-cher' 부분은 '처', '쳐', 또는 '커' 등으로 발음이 달라지는 등 사람마다 읽는 방식이 매우 다양하다. 백준의 '단계별로 풀어보기' 탭에서는 '마나허'라고 표기한 적도 있었으나 토론 끝에 '매니커'로 바뀌었다.

---

문자열에서 팰린드롬 부분 문자열을 찾을 때 시작점이나 끝점을 고정하면 굉장히 복잡해지기 때문에 일반적으로는 중심을 고정하고 좌우 문자들을 차례로 비교한다. 또한 그냥 중심을 고정하면 길이가 짝수인 팰린드롬을 찾지 못하기 때문에 처음에 각각의 문자들 사이에 동일한 문자(일반적으로 '#' 문자를 사용한다)를 하나씩 넣는다. 이렇게 하면 길이가 짝수인 팰린드롬도 찾을 수 있다. 구현하면 다음과 같으며 $d$ 배열은 $s_i$를 중심으로 하는 가장 긴 팰린드롬의 길이가 $2d[i]+1$이라는 의미이다. (실제로는 추가된 '#' 문자의 개수를 다시 빼는 과정이 필요하지만, Naive 코드가 이 글의 주 목적이 아니기 때문에 그것에 대한 구현은 넣지 않았다.)

#import<bits/stdc++.h>
using namespace std;
int d[200004];
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    s += s.substr(1);
    for(int i = n - 1; i; i--)
    {
        s[2 * i] = s[i];
        s[2 * i - 1] = '#';
    }
    n = s.size();
    for(int i = 0; i < n; i++)
    {
        while(i - d[i] - 1 >= 0 && i + d[i] + 1 < n && s[i - d[i] - 1] == s[i + d[i] + 1])d[i]++;
    }
}

하지만 이 방법의 시간복잡도는 $O(n^2)$으로, 한 가지 문자로만 이루어진 문자열 같은 특수한 경우 문자열의 길이가 길어지면 성능이 떨어질 수 있다.

---

Manacher 알고리즘은 $d[i]$를 $0$부터 증가시키지 않고 앞에서 구한 $d[i]$값들을 이용해서 $d[i]$의 초기값을 설정함으로써 반복 횟수를 줄인다. 우선 $d[0] = 0$임은 쉽게 알 수 있고, $p = v = 0$으로 초기화하고 다음과 같은 방법으로 $d[1]$부터 $d[n - 1]$까지를 차례로 구한다. 이때 $p$는 이전까지 구한 팰린드롬 중 가장 오른쪽에서 끝나는 것의 중심이며, $v$는 그 팰린드롬이 끝나는 지점이다.

    1. $i > v$인 경우 $d[i]$의 초기값은 $0$이다.

    2. $i \le v$인 경우, $s_i$가 $p$를 중심으로 하는 가장 긴 팰린드롬에 포함된다는 의미이므로 이 팰린드롬에서 $s_i$의 대칭점 $s_{2p-i}$가 존재한다는 것을 알 수 있다. 따라서 $d[2p - i]$의 값을 $d[i]$의 초기값으로 할 수 있는데, $p$를 중심으로 가장 긴 팰린드롬보다 뒤에 나오는 문자들은 직접 확인해야 한다. 따라서 $d[i]$의 최종 초기값은 $\min(d[2p - i], v - i)$이다.

    3. 앞에서 Naive한 방법으로 구했던 것과 비슷하게 $d[i]$를 가능한 만큼 증가시킨다. 만약 $i + d[i]$가 $v$보다 커졌다면 $p = i$, $v = i + d[i]$로 값들을 갱신한다.

이렇게 해서 구해진 $d[i]$는 '#'의 개수를 포함하므로 '#'의 개수를 뺀 실제 팰린드롬의 길이로 변환하는 과정이 필요하다. 변환은 다음과 같은 방법으로 할 수 있다.

• $i$가 짝수, $d[i]$가 짝수인 경우 $s_i$를 중심으로 하는 가장 긴 팰린드롬에서 '#'이 아닌 문자의 수는 $d[i]+1$이다.
• $i$가 짝수, $d[i]$가 홀수인 경우 $s_i$를 중심으로 하는 가장 긴 팰린드롬에서 '#'이 아닌 문자의 수는 $d[i]$이다.
• $i$가 홀수, $d[i]$가 짝수인 경우 $s_i$를 중심으로 하는 가장 긴 팰린드롬에서 '#'이 아닌 문자의 수는 $d[i]$이다.
• $i$가 홀수, $d[i]$가 홀수인 경우 $s_i$를 중심으로 하는 가장 긴 팰린드롬에서 '#'이 아닌 문자의 수는 $d[i]+1$이다.

따라서 $i$와 $d[i]$의 홀짝이 같을 때만 $d[i]$에 $1$을 더하면 된다. 전체적인 구현은 다음과 같다.

#import<bits/stdc++.h>
using namespace std;
int p, v, d[200004];
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    s += s.substr(1);
    for(int i = n - 1; i; i--)
    {
        s[2 * i] = s[i];
        s[2 * i - 1] = '#';
    }
    n = s.size();
    for(int i = 1; i < n; i++)
    {
        if(i <= v)d[i] = min(d[2 * p - i], v - i);
        while(i - d[i] - 1 >= 0 && i + d[i] + 1 < n && s[i - d[i] - 1] == s[i + d[i] + 1])
            d[i]++;
        if(i + d[i] > v)
        {
            p = i;
            v = i + d[i];
        }
    }
    for(int i = 0; i < n; i++)d[i] += i % 2 == d[i] % 2;
}

$v$를 따로 분리하지 않고 다음과 같이 구현할 수도 있다.

#import<bits/stdc++.h>
using namespace std;
int p, d[200004];
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    s += s.substr(1);
    for(int i = n - 1; i; i--)
    {
        s[2 * i] = s[i];
        s[2 * i - 1] = '#';
    }
    n = s.size();
    for(int i = 1; i < n; i++)
    {
        d[i] = max(0, min(d[2 * p - i], p + d[p] - i));
        while(i - d[i] - 1 >= 0 && i + d[i] + 1 < n && s[i - d[i] - 1] == s[i + d[i] + 1])
            d[i]++;
        if(i + d[i] > p + d[p])p = i;
    }
    for(int i = 0; i < n; i++)d[i] += i % 2 == d[i] % 2;
}

Manacher 알고리즘의 시간복잡도는 다음과 같이 계산할 수 있다.

• 반복 과정에서 $i \le v$이고 $d[i] = d[2p - i] < v - i$일 경우 while문이 처음부터 거짓이 되어 $d[i]$가 더이상 증가하지 않는다.
• 그렇지 않을 경우 while문 내에서 $d[i]$가 $1$씩 증가할 때마다 $v$도 $1$씩 증가한다. 이때 $v$의 초기값이 $0$이고 $v$가 $n$ 이상이 될 수 없으므로 while문 내부는 최대 $n-1$번 실행된다. 나머지 for문의 실행 횟수 역시 $n$에 비례하므로 전체 시간 복잡도는 $\Theta(n)$이다.

[연습문제]

 

BOJ 13275. 가장 긴 팰린드롬 부분 문자열 (Platinum V)

Manacher 알고리즘을 사용하는 기본 문제. $d[i]$의 최댓값이 답이 된다. 14444번과 똑같은 문제이다.

 

BOJ 16163. #15164번_제보 (Platinum V)

이번에는 모든 $d[i]$의 합이 답이 된다.

 

BOJ 11046. 팰린드롬?? (Platinum V)

$d[i]$를 전부 구한 다음 각각의 $S$와 $E$의 중간 지점을 중심으로 하는 가장 긴 팰린드롬의 길이가 얼마인지를 확인하면서 쿼리를 처리하면 된다.

 

CF 1326D2. Prefix-Suffix Palindrome (Hard version) (1800)

$s$의 양 끝에 같은 문자가 존재하면 최대한 많이 선택한다. 그리고 나서 가운데에 남은 문자열이 존재할 경우, 그 문자열의 양 끝 중 한 쪽을 포함하는 가장 긴 팰린드롬을 찾는다. 이제 앞에서 선택한 문자들을 앞뒤로 붙여주면 된다. 여기서는 Manacher를 이용한 풀이를 제시했지만 KMP로도 풀 수 있다.

 

→ solved.ac tag: manacher