Manacher의 알고리즘과 Z 알고리즘

Manacher의 알고리즘과 Z 알고리즘을 따로따로 공부했었다. 보면서 참 공통점이 많은 알고리즘이라는 생각이 들었다. 풀고자 하는 문제도 다른 듯 하면서 유사하게 정의된다. 문자열 내에서 DP 식을 세우고, 이전까지 한 계산들의 끝점을 이용해 부분문제를 만들어, 시간 복잡도를 선형으로 만드는 알고리즘이다. 원래 문자열 알고리즘들은 이해하기 복잡하다는 이유로 별로 좋아하지 않았는데, 이 두 알고리즘은 흥미로운 구석이 많았다.

 

 

1. Manacher's Algorithm

 

[문제] 길이 $n$의 문자열 $S$가 주어진다. 이 때, $0\le i<n$인 $i$에 대해 $p_i$를 $S[i-k .. i+k]$가 팰린드롬인 가장 큰 $k$의 값으로 정의한다. $p_i$를 모든 $i$에 대해 구하라.

 

그러니까, 문제는 문자열이 주어질 때, 각 문자를 중심으로 하는 팰린드롬의 최대 길이를 구하는 문제와 같다. 문자열 "abcbcbc"에 대한 답은 $[0, 0, 1, 2, 2, 1, 0]$이 된다. 각 문자를 중심으로 하는 가장 긴 팰린드롬이 각각 [a, b, bcb, bcbcb, cbcbc, cbc, c]이기 때문이다.

 

Naive한 알고리즘은, 각 문자를 중심으로 시작하면서, $k=p[i]$를 $0$부터 시작해 $S[i-k-1] = S[i+k+1]$가 성립하지 않을 때까지 $k$를 $1$씩 늘여 나가는 것이다. 이 방법의 시간 복잡도는 최악의 경우에 $O(n^2)$이다.

 

void palindrome(string s, int *p) {
    int n = s.size();
 
    for (int i=0; i<n; i++) 
        while (i-p[i]-1>=0 and i+p[i]+1<n and s[i-p[i]-1] == s[i+p[i]+1]) p[i]++;
}
 

 

Manacher의 알고리즘은 $k$를 $0$부터 시작하지 않고 특정 시작점을 잡아서 이 시작점부터 증가시켜도 됨을 주장한다. 현재 $p[i]$를 계산하고 있는 시점에서, $r = \max_{j=0..i-1}(j+p_j)$로, 이 때 $p$의 값을 $j$로 정의하자. (과정을 시작하기 전 초기 상태는 $r=-1$이라고 생각하자) 즉, $r$은 현재까지 발견된 가장 오른쪽에서 끝나는 팰린드롬의 끝점의 위치이다.

 

i) $i\le r$이라면, $i$는 $k$를 중심으로 하는 팰린드롬 안에 위치하고, $i$의 팰린드롬 상의 반대 점인 $2k-i$가 존재한다. $2k-i$를 중심으로 하는 팰린드롬은 대칭되는 점인 $i$를 중심으로도 팰린드롬을 이룬다. 이미 구해온 $p_{2k-i}$를 이용해 $p_i \leftarrow \min(p_{2k-i}, r-i)$로 초기화할 수 있다.

ii) $i>r$이라면, 이전의 계산 과정에서 $p$에서 시작하는 팰린드롬에 대한 힌트를 얻을 수 없고, $p_i = 0$으로 초기화한다.

 

위의 과정으로 $p_i$를 초기화했다면, 앞서 말한 naive 알고리즘과 같이 $S[i-p[i]-1] = S[i+p[i]+1]$가 성립하지 않을 때까지 $p[i]$를 증가시켜주면 된다.

 

void palindrome(string s, int *p) {
    int n = s.size(), r = -1, k = -1;
 
    for (int i=0; i<n; i++) {
        if (i<=r) p[i] = min(r-i, p[2*k-i]);
        while (i-p[i]-1>=0 and i+p[i]+1<n and s[i-p[i]-1] == s[i+p[i]+1]) p[i]++;
        if (r < i+p[i]) r = i+p[i], k = i;
    }
}
 

 

* 이해가 안 된다면 Z 알고리즘에 대한 설명을 읽으면 이것도 이해가 될 수도 있다.

 

위 알고리즘은 놀랍게도 최악의 경우 시간 복잡도 $O(n)$에 작동하게 된다. 증명은 $p[i]$의 증가가 이루어질 때마다 $r$ 값이 1씩 증가한다는 사실로 가능하다. 내부에 있는 while문의 실행 시간은 모두 합쳐서 $O(n)$이 된다. 실행될 때마다 $r$이 1씩 증가하고 $r$은 최대 $n$까지만 증가할 것이니. 바깥에 있는 for문은 자명히 $O(n)$ 시간을 소요하므로 전체 시간 복잡도는 $O(n)$이다.

 

참고. 이 알고리즘은 각 글자를 중심으로 하는 팰린드롬의 길이만을 구하기 때문에, 길이가 짝수인 팰린드롬을 구할 수 없다. 짝수인 팰린드롬도 세고 싶다면, 각 문자 사이에 더미 문자를 끼워넣어 (ex. abcbbc -> a#b#c#b#b#c)로 바꾸면, 길이가 짝수인 팰린드롬은 # 문자를 중심으로 하는 팰린드롬으로 세어지게 된다.

 

출처 및 참고: #

 

 

2. Z Algorithm

 

[문제] 길이 $n$의 문자열 $S$가 주어진다. 이 때, $0\le i<n$인 $i$에 대해 $p_i$를 $S[0 .. k] = S[i .. i+k]$인 가장 큰 $k$의 값으로 정의한다. $p_i$를 모든 $i$에 대해 구하라.

 

이 문제 또한 문자열이 주어질 때, 각 $i$에 대해 $i$번째부터 시작하는 부분 문자열의 접두사 $S[i..i+k]$와 전체 문자열의 접두사 $S[0..k]$가 같은 최대 길이를 구하는 문제가 된다. $k=0$일 때도 $S[i] \neq S[0]$이라면, $p_i = -1$로 하자.

 

이 역시 Manacher 알고리즘과 거의 같은 방식으로 작동한다. 여기에도 이때까지 구한 $i+p[i]$, 즉 구한 문자열의 접두사의 오른쪽 끝의 위치 값들 중 가장 큰 값을 놓고 초기값을 정하는 과정을 사용한다. 간단히 요약하면 다음과 같다.

 

0. $i$를 $0..n-1$까지 진행한다. 아래는 $p[0..i-1]$이 모두 구해졌을 때 $p[i]$를 구하는 과정이다.

1. $r = \max_{j=0..i-1}(j+p[j])$라 하고, 이 때의 $j$를 $l$이라 하자. $S[l..r]$은 같은 길이의 접두사 $S[0..r-l]$과 같다.

2. $p[i]$의 초기값을 결정한다.

 2-1. $i \le r$이라면, $p[i] \leftarrow min(r-i, p[i-l])$

 2-2. $i > r$이라면, $p[i] \leftarrow -1$

3. $S[i+p[i]+1] = S[p[i]+1]$이 성립하지 않을 때까지 $p[i]$를 계속 1씩 증가시킨다.

 

void prefix(string s, int *p) {
    int n = s.size(), l = -1, r = -1;
 
    for (int i=1; i<n; i++) {
        if (i<=r) p[i] = min(r-i, p[i-l]);
        while (i+p[i]+1<n and s[i+p[i]+1] == s[p[i]+1]) p[i]++;
        if (r < i+p[i]) r = i+p[i], l = i;
    }
}
 

 

3번에서 $p[i]$를 증가할 때마다 $r$이 증가하기 때문에 도합 $O(n)$의 시간 복잡도로 돌아가리란 것을 알 수 있다.

 

출처 및 참고: #

 

연습문제:

- 13713: 문자열과 쿼리