Manacher 알고리즘

1975년에 발표된 Manacher 알고리즘은 "특정 문자를 중심으로 하는 팰린드롬 중 가장 긴 홀수 팰린드롬의 길이"를 찾는 알고리즘이다.

 

Manacher알고리즘은 Polynomial time을 가지는 문자열 알고리즘과 동일하게 "이미 탐색한 것에 대해서는 다시 돌아보지 않는다는 측면"에서 맥이 같다고 볼 수 있다.

 

Manacher알고리즘은 팰린드롬에서 가지는 대칭성을 이용하여 이전에 한번 탐색한 구간에 대해서 이전에 구했던 정보를 활용한다.

예를 들어서 다음과 같은 경우가 있을 것이다. 여기서 [L, R]은 이전까지 탐색했던 범위라고 가정을 하자.

즉 j < i 인 j 에 대하여, 이미 j번째에서 [L,R] 구간까지 탐색을 완료했다는 뜻이 된다.

그리고 현재, 우리는 i번째 문자에 대하여 "i번째 문자를 중심으로 하는 팰린드롬 중 가장 긴 홀수 팰린드롬의 길이의 절반" 을 찾고싶다.

{ 이것을 dp[i] 라고 정의하자,  "i를 중심으로 한 가장 긴 홀수 팰린드롬의 길이"를 x라 한다면 i = (x+1)/2 가 된다. }

홀수 길이의 팰린드롬의 길이의 절반은 float로 떨어지게 되고, 이를 처리하기 위해서 내림/올림 처리를 해주어야하는데 

올림 처리를 하여서 길이가 1인 팰린드롬도 직관적으로 표현하였다.

이것을 표현한 그림은 다음과 같다.

이것을 통해 무엇을 알 수 있을까? 

중심점(=대칭점)인 j에 대하여 i와 대칭인 점 i'을 생각해보도록 하자. 

 

[L,R]구간내에서 팰린드롬을 만족할 때 팰린드롬의 대칭성에 대한 성질에 따라,

S[i'] = S[i] 이고 또한 S[i' - k] = S[i + k] {단, i' - k >= L and i + k <= R} 인 것을 알 수 있다.

 

그렇다면, i를 중심으로 하는 홀수개의 팰린드롬의 최대 인덱스가 R범위 내에만 있다면 i'에서 구한 i'를 중심으로 하는 홀수개의 팰린드롬의 개수와 동일하다는 의미가 되므로 뒤를 살펴볼 필요없이 해당 값을 재활용하면 된다는 것을 의미한다.

 

i < R and i + dp[i'] <= R

즉, 위와 같은 상황 일 경우 이전의 정보를 그대로 활용하여 불필요한 탐색을 줄일 수 있다.

그렇지 않은 경우, 우리는 Naive하게 탐색을 진행 해주어야한다.

---

자 여기까지 기본적인 원리에 대하여 알아보았다. 

보다 더 자세한 설명을 위해 정의를 살펴보고 가자.

 

1. dp[i] : i를 중심으로 하는 가장 긴 홀수 팰린드롬의 길이를 x라 하였을 때, (x+1)/2
               즉 대칭점을 포함한 오른쪽 구간의 길이 (dp[i]) 

2. 0 <= i < N 순서대로 dp table을 채워나간다.

3. 0 <= j < i 인 j중 j+dp[j]가 max가 되는 j를 p라고 가정하고
이 때, 팰린드롬의 범위[ p - dp[i] + 1, p + dp[j] - 1 ] 을 [ L, R ] 이라고 칭한다.

 

1.  대칭성을 이용할 수 있을 때
   1. 추가적인 탐색이 필요 없는 경우
   2. 추가적인 탐색이 필요한 경우
2.  대칭성을 이용할 수 없을 때

 

 

Case 1-1 ) 대칭성 이용 O , 추가적인 탐색이 필요 없는 경우 { i < R && i + dp[i'] <= R } 

앞에서 설명한 대로 dp[i] = dp[i'] 가 된다.

홀수 크기의 구간에 대해서 대칭점(cp)를 하나로 잡을 수 있다.

i' = cp - ( i - cp ) 와 같고 cp = ( L + R ) / 2 이므로,  i' = L+R-i 가 된다.

if( i <= R && i + dp[L+R-i] <= R )
	dp[i] = dp[L+R-i];

 

Case 1-2) 대칭성 이용 O, 추가적인 탐색이 필요한 경우 { i < R && i + dp[i'] > R } 

 

다음과 같이 이전까지 탐색한 구간 [oldL, oldR] 범위를 넘어가는 경우 해당 범위 밖을 벗어나는 범위에 대해서는 대칭성을 보장하지 않는다.

그러므로 oldR 범위부터 한칸 씩 크기를 늘려가며 Naive하게 탐색하는 과정이 필요하다.

if( i < R && i + dp[L+R-i] > R ){
	int sz = r - i + 1; // size
   	while( i - sz >= 0 && i + sz < n && S[i-sz] == S[i+sz] )
    	sz += 1;
    dp[i] = sz--;   
	if( i + sz > r ){
    	l = i - sz;
        r = i + sz;
    }
}

커버할 수 있는 구간의 범위가 바뀌었으므로, 구간[L,R]을 갱신하는 과정도 필요하다.

 

 

 

Case 2) 대칭성을 이용할 수 없을 때 ( i > R )

이 경우도 Naive 하게 탐색하는 과정이 필요하다.

if( i > R ){
	int sz = 1;
    while( i - sz >= 0 && i + sz < n && S[i-sz] == S[i+sz] )
    	sz += 1;
	dp[i] = sz--;
    if( i + sz > r ){
    	l = i - sz;
        r = i + sz;
    }
}

 

 

전체코드

#include <bits/stdc++.h>
using namespace std;
int n;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    string S;
    cin >> S;
    n = S.size();

    vector<int> odd_dp(n);

    int l = 0, r = -1;
    // 홀수 크기의 팰린드롬에 대하여 고려
    for(int i=0; i<n; i++){
        int sz = ( i > r ) ? 1 : min(r-i+1, odd_dp[l+r-i]);
        while( i - sz >= 0 && i + sz < n && S[i-sz] == S[i+sz] )
            sz += 1;
        odd_dp[i] = sz--;
        if( i + sz > r ){
            l = i - sz;
            r = i + sz;
        }
    }

    return 0;
}

 

 

 

Naive 한 Manacher 알고리즘은 대칭점(cp)를 하나로 잡고 양옆으로 1개씩 확장시켜나가는 구조를 가지기 때문에, 짝수 길이의 팰린드롬은 고려해 줄 수 없다. 짝수 길이의 팰린드롬은 대칭점(cp)를 2개로 잡는 것을 통해 해결 할 수 있다.

짝수 길이의 팰린드롬에 대하여 고려한 코드는 다음과 같다.

    for(int i=0; i<n; i++){
        int sz = ( i > r ) ? 0 : min(r-i+1, even_dp[l+r-i-1]);
        while( i - sz - 1 >= 0 && i + sz < n && S[i-sz-1] == S[i+sz] )
            sz += 1;

        even_dp[i] = sz--;
        if( i + sz > r ){
            l = i - sz - 1;
            r = i + sz;
        }
    }

cp1-i, cp2+i 로 확장 해 나가면서 Naive하게 탐색하기 때문에 인덱스 범위에 유의하자.