Manacher 알고리즘 - $O(N)$에 모든 부분 회문 찾기¶

문제¶

길이가 $n$인 문자열 $s$가 주어집니다. 부분 문자열 $s[i\dots j]$가 회문이 되는 모든 쌍 $(i, j)$를 찾으십시오. 문자열 $t$는 $t = t_{rev}$일 때 회문입니다($t_{rev}$는 $t$를 뒤집은 문자열입니다).

더 정확한 문제 서술¶

최악의 경우 문자열에는 최대 $O(n^2)$개의 회문 부분 문자열이 있을 수 있으므로, 언뜻 보기에는 이 문제를 선형 시간에 푸는 알고리즘이 없는 것처럼 보입니다.

하지만 회문에 대한 정보는 압축된 형태로 저장할 수 있습니다. 각 위치 $i$에 대해 이 위치를 중심으로 하는 비어 있지 않은 회문의 개수를 구하는 것입니다.

중심이 같은 회문들은 연속된 사슬을 이룹니다. 즉, $i$를 중심으로 하는 길이 $l$의 회문이 있으면, 역시 $i$를 중심으로 하는 길이 $l-2$, $l-4$ 등의 회문도 존재합니다. 따라서 이러한 방식으로 모든 회문 부분 문자열에 대한 정보를 모읍니다.

길이가 홀수인 회문과 짝수인 회문은 각각 $d_{odd}[i]$와 $d_{even}[i]$로 따로 셉니다. 길이가 짝수인 회문의 경우, 가운데 두 문자가 $s[i]$와 $s[i-1]$이면 위치 $i$를 중심으로 한다고 간주합니다.

예를 들어, 문자열 $s = abababc$에는 위치 $s[3] = b$를 중심으로 하는 길이가 홀수인 회문이 세 개 있습니다. 즉, $d_{odd}[3] = 3$입니다:

$$a\ \overbrace{b\ a\ \underbrace{b}_{s_3}\ a\ b}^{d_{odd}[3]=3} c$$

그리고 문자열 $s = cbaabd$에는 위치 $s[3] = a$를 중심으로 하는 길이가 짝수인 회문이 두 개 있습니다. 즉, $d_{even}[3] = 2$입니다:

$$c\ \overbrace{b\ a\ \underbrace{a}_{s_3}\ b}^{d_{even}[3]=2} d$$

이러한 "회문성 배열" $d_{odd}[]$와 $d_{even}[]$를 선형 시간에 계산하는, 충분히 간단한 알고리즘이 존재한다는 것은 놀라운 사실입니다. 이 글에서는 그 알고리즘을 설명합니다.

풀이¶

일반적으로 이 문제에는 여러 풀이가 있습니다. 문자열 해싱을 사용하면 $O(n\cdot \log n)$에 풀 수 있고, 접미사 트리와 빠른 LCA를 사용하면 $O(n)$에 풀 수 있습니다.

하지만 여기서 설명하는 방법은 훨씬 더 간단하며, 시간 및 메모리 복잡도에 숨어 있는 상수도 더 작습니다. 이 알고리즘은 1975년에 Glenn K. Manacher가 발견했습니다.

이 문제를 풀고 회문 전반을 다루는 또 다른 현대적인 방법은 이른바 회문 트리, 즉 eertree를 사용하는 것입니다.

단순한 알고리즘¶

이후 설명에서 모호함을 피하기 위해 "단순한 알고리즘"이 무엇인지 정의합니다.

이는 다음과 같이 동작하는 알고리즘입니다. 각 중심 위치 $i$에 대해, 매번 대응하는 문자 한 쌍을 비교하면서 가능한 한 계속 답을 1씩 늘려 봅니다.

이러한 알고리즘은 느려서 $O(n^2)$에만 답을 계산할 수 있습니다.

단순한 알고리즘의 구현은 다음과 같습니다:

vector<int> manacher_odd_trivial(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    for(int i = 1; i <= n; i++) {
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

문자열의 양 끝을 따로 처리하지 않기 위해 종단 문자 $와 ^를 사용했습니다.

Manacher 알고리즘¶

길이가 홀수인 모든 부분 회문을 찾는 알고리즘, 즉 $d_{odd}[]$를 계산하는 알고리즘을 설명합니다.

빠른 계산을 위해 지금까지 찾은 가장 오른쪽 (부분) 팰린드롬의 배타적 경계 $(l, r)$을 유지합니다(즉, 현재 가장 오른쪽 (부분) 팰린드롬은 $s[l+1] s[l+2] \dots s[r-1]$입니다). 처음에는 $l = 0, r = 1$로 설정하며, 이는 빈 문자열에 해당합니다.

이제 다음 $i$에 대해 $d_{odd}[i]$를 계산하려고 하며, $d_{odd}[]$의 이전 값은 모두 이미 계산되어 있습니다. 다음과 같이 진행합니다.

$i$가 현재 부분 회문의 바깥에 있으면, 즉 $i \geq r$이면, 단순한 알고리즘을 그대로 실행합니다.

즉, $d_{odd}[i]$를 하나씩 증가시키면서 매번 현재 가장 오른쪽 부분 문자열 $[i - d_{odd}[i]\dots i + d_{odd}[i]]$가 팰린드롬인지 확인합니다. 처음으로 불일치를 찾거나 $s$의 경계에 도달하면 멈춥니다. 이 경우 $d_{odd}[i]$의 계산이 끝납니다. 그 후에는 $(l, r)$을 갱신하는 것을 잊지 말아야 합니다. $r$은 현재 가장 오른쪽에 있는 부분 회문의 오른쪽 경계(경계 자체는 포함하지 않음)를 나타내도록 갱신해야 합니다(따라서 그 마지막 인덱스는 $r - 1$입니다).
이제 $i \le r$인 경우를 생각해 봅시다. 이미 계산된 $d_{odd}[]$의 값에서 정보를 얻어 보겠습니다. 그러면 부분 회문 $(l, r)$ 안에서 $i$의 "거울" 위치를 찾아봅시다. 즉, 위치 $j = l + (r - i)$를 구하고 $d_{odd}[j]$의 값을 확인합니다. $j$는 $(l+r)/2$를 기준으로 $i$와 대칭인 위치이므로, 거의 항상 $d_{odd}[i] = d_{odd}[j]$로 대입할 수 있습니다. 이를 나타낸 그림입니다($j$를 중심으로 하는 팰린드롬이 실제로 $i$를 중심으로 하는 팰린드롬에 "복사"됩니다).

$$ \ldots\ \overbrace{ s_{l+1}\ \ldots\ \underbrace{ s_{j-d_{odd}[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_{odd}[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ s_{r-1}\ }^\text{palindrome}\ \ldots $$

하지만 올바르게 처리해야 하는 까다로운 경우가 있습니다. "안쪽" 팰린드롬이 "바깥쪽" 팰린드롬의 경계에 도달하는 경우, 즉 $j - d_{odd}[j] \le l$인 경우(또는 같은 말로 $i + d_{odd}[j] \ge r$인 경우)입니다. "바깥쪽" 팰린드롬 밖에서는 대칭성이 보장되지 않으므로, 단순히 $d_{odd}[i] = d_{odd}[j]$로 대입하면 틀립니다. 위치 $i$의 팰린드롬이 같은 길이를 가진다고 말할 수 있을 만큼 충분한 정보가 없기 때문입니다.

사실 이러한 상황을 올바르게 처리하려면 일단 팰린드롬의 길이를 제한해야 합니다. 즉, $d_{odd}[i] = r - i$로 대입합니다. 그 후 가능한 한 $d_{odd}[i]$를 증가시키려고 시도하는 단순한 알고리즘을 실행합니다.

이 경우를 나타낸 그림입니다(중심이 $j$인 팰린드롬이 "바깥쪽" 팰린드롬에 들어맞도록 제한됩니다).

$$ \ldots\ \overbrace{ \underbrace{ s_{l+1}\ \ldots\ s_j\ \ldots\ s_{j+(j-l)-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)+1}\ \ldots\ s_i\ \ldots\ s_{r-1} }_\text{palindrome}\ }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here} $$

그림에서 볼 수 있듯이 중심이 $j$인 팰린드롬은 더 길어서 "바깥쪽" 팰린드롬 밖으로 나갈 수도 있지만, $i$를 중심으로 할 때는 "바깥쪽" 팰린드롬 안에 완전히 들어가는 부분만 사용할 수 있습니다. 하지만 위치 $i$에 대한 답($d_{odd}[i]$)은 이 부분보다 훨씬 클 수 있으므로, 다음으로 단순한 알고리즘을 실행하여 이를 "바깥쪽" 팰린드롬 밖으로, 즉 "try moving here" 영역으로 늘려 봅니다.

다시 말하지만, 각 $d_{odd}[i]$를 계산한 후에는 $(l, r)$ 값을 갱신하는 것을 잊지 말아야 합니다.

Manacher 알고리즘의 복잡도¶

특정 위치의 답을 찾는 동안 나이브한 알고리즘을 자주 실행하므로, 언뜻 보기에는 이 알고리즘이 선형 시간 복잡도를 가진다는 것이 분명하지 않습니다.

그러나 좀 더 주의 깊게 분석하면 이 알고리즘이 선형임을 알 수 있습니다. 실제로 이 알고리즘과 비슷해 보이는 Z-함수 구성 알고리즘도 선형 시간에 동작합니다.

단순한 알고리즘의 매 반복마다 $r$이 1씩 증가한다는 것을 알 수 있습니다. 또한 알고리즘이 진행되는 동안 $r$은 감소할 수 없습니다. 따라서 단순한 알고리즘은 전체적으로 $O(n)$번 반복합니다.

Manacher 알고리즘의 나머지 부분은 분명히 선형 시간에 동작합니다. 따라서 $O(n)$ 시간 복잡도를 얻습니다.

Manacher 알고리즘의 구현¶

$d_{odd}[]$를 계산하는 코드는 다음과 같습니다. 유의할 점은 다음과 같습니다.

$i$는 현재 팰린드롬의 중심 문자의 인덱스입니다.
$i$가 $r$을 초과하면 $d_{odd}[i]$는 0으로 초기화됩니다.
$i$가 $r$을 넘지 않으면, $d_{odd}[i]$는 $d_{odd}[j]$로 초기화되거나(여기서 $j$는 $(l,r)$에서 $i$의 대칭 위치입니다), $d_{odd}[i]$가 "바깥" 팰린드롬의 크기로 제한됩니다.
while 루프는 자명한 알고리즘을 나타냅니다. $k$의 값과 관계없이 이 루프를 실행합니다.
$i$를 중심으로 하는 팰린드롬의 크기가 $x$이면, $d_{odd}[i]$에는 $\frac{x+1}{2}$가 저장됩니다.

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for(int i = 1; i <= n; i++) {
        if(i <= r) {
            p[i] = min(r - i, p[l + (r - i)]);
        }
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

홀짝성 다루기¶

Manacher 알고리즘을 홀수 길이와 짝수 길이에 대해 각각 따로 구현할 수도 있지만, 짝수 길이 버전은 덜 자연스럽고 off-by-one 오류를 일으키기 쉬워서 구현하기 더 어렵다고 여겨지는 경우가 많습니다.

이를 완화하기 위해, 전체 문제를 홀수 길이의 팰린드롬만 다루는 경우로 환원할 수 있습니다. 이렇게 하려면 문자열의 각 문자 사이와 문자열의 시작과 끝에 # 문자를 추가로 넣으면 됩니다.

$$abcbcba \to \#a\#b\#c\#b\#c\#b\#a\#,$$

$$d = [1,2,1,2,1,4,1,8,1,4,1,2,1,2,1].$$

보시다시피 $d[2i]=2 d_{even}[i]+1$이고 $d[2i+1]=2 d_{odd}[i]$입니다. 여기서 $d$는 #으로 이어 붙인 문자열에서 홀수 길이 팰린드롬에 대한 Manacher 배열을 나타내고, $d_{odd}$와 $d_{even}$은 원래 문자열에서 위에서 정의한 배열에 해당합니다.

실제로 # 문자는 홀수 길이 팰린드롬에 영향을 주지 않으며, 이 팰린드롬들은 여전히 원래 문자열의 문자를 중심으로 합니다. 하지만 이제 원래 문자열의 짝수 길이 팰린드롬은 새 문자열에서 # 문자를 중심으로 하는 홀수 길이 팰린드롬이 됩니다.

$d[2i]$와 $d[2i+1]$은 본질적으로 각각 $i$를 중심으로 하는 가장 긴 홀수 길이 팰린드롬과 짝수 길이 팰린드롬의 길이에 $1$을 더한 값이라는 점에 유의하십시오.

환원은 다음과 같이 구현됩니다.

vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

간단히 하기 위해 배열을 $d_{odd}$와 $d_{even}$으로 나누는 부분과 이들을 명시적으로 계산하는 부분은 생략합니다.