Manacher's Algorithm

Palindrome

문자열이 있을 때 뒤집어도 같은 문자열이라면 이 문자열을 회문(palindrome)이라고 부른다. 예를 들어, "mom", "tattarrattat", "IOI" 등이 있다. 문자열이 palindrome인지 확인하는 방법은 최소 한 번은 스캔해야 하기 때문에 $O(n)$의 시간 복잡도를 가진다.

 

부분 문자열의 palindrome

그러면 어떤 문자열이 있을 때 palindrome을 만족하는 부분 문자열도 있을 것이다. 한 글자만 놓고 보면 길이가 1인 palindrome을 만족할 테니, 의미 있게 임의의 위치를 중심으로 만들 수 있는 가장 긴 palindrome을 생각해보자.

 

처음 생각나는 방법은 무식하게 전부 해보는 방법이다.
길이가 1인 palindrome이 있는지 확인하고, 있다면 2에 대해서 확인해보고, 있다면 3, 4, ..., n까지 다 해보면 된다. 뭔가 계산하는 과정에서 뭔가 중복되는 느낌이 있다.
이미 길이 i에 대해서 palindrome이 있는지 확인했다면, 길이 i+1에 대한 palindrome을 확인할 때는 이전 정보를 이용하면 더 빠르게 구할 수 있을 것이다. 하지만 모든 길이, 모든 위치에 대해서 구해야 하는 전제는 바뀌지 않는다.

 

여기서 더 나아가 중복 검사를 더 세련되게 하고, 필요없는 탐색은 애초에 제거해버리면 획기적으로 빠르게 구할 수 있다.

 

Manacher's Algorithm

Manacher's Algorithm으로 모든 위치에서 만들 수 있는 가장 긴 palindrome길이를 $O(n)$만에 구할 수 있다. 즉, 하나의 문자열이 palindrome인지 확인하는 데 $O(n)$임에도 불구하고, 더 복잡한 문제를 같은 수준으로 풀 수 있다.

 

어떻게 하면 필요없는 계산을 제거해서 빠르게 구할 수 있는지 보자.

[0, i-1]에 대해서 각 위치를 중심으로 가능한 최대 palindrome의 길이 d[0..i-1]를 구했다고 가정하고, d[i]를 어떻게 이전 값을 재활용해서 효율적으로 구하는지 알아보자. [0, i-1]를 만족하는 위치 p에서 d[p]를 구할 때 palindrome이 충분히 길었으면 이미 i위치를 한번 탐색했을 것이고, 그렇지 않다면 탐색하지 않았을 것이다.

 

첫 번째 case

아래와 같이 i가 아직 이전에 탐색해보지 않은 경우가 있다.

아직 탐색해보지 않았기 때문에 재활용이 불가능하고, 이 경우는 i부터 반지름을 늘려가며 탐색을 해볼 수밖에 없다.

 

두 번째 case

i 이전 단계에서 i보다 큰 범위를 한번 탐색한 경우가 있다. 최대로 탐색했던 중심 위치를 p라고 했을 때, 아래는 d[p] = 5 인 경우이다.

이 경우에는 이전에 구한 값을 재활용할 수 있다. d[p]를 중심으로 양옆으로 5까지는 문자열이 palindrome이라는 사실을 알고 있다. i를 중심으로하는 palindrome을 탐색하기 위해 이미 구했던 p를 중심으로 i와 대칭점에 있는 i'를 이용할 수 있다.

 

이때 i'를 중심으로 하는 palindrome이 p를 중심으로 하는 palindrome에 속하는지 여부에 따라 경우를 나눌 수 있다.

1) i' - d[i'] >= p - d[p] 인 경우
d[i] = d[i']임을 알 수 있다.

왜냐하면 str[i - d[i'] - 1] == str[i + d[i'] + 1] 을 만족한다면 d[i'] 더 커질 수 있다는 뜻이고, 그렇다면 p를 중심으로 하는 palindrome에 속한다는 가정이 거짓이 되기 때문이다.

2) i' - d[i'] < p - d[p] 인 경우
d[i] >= p + d[p] - i 라는 사실을 알 수 있다.
더 커질 수 있는지는 아직 탐색해보지 않은 p+d[p]+1부터 비교해봐야 알 수 있다.

 

이전에 구한 값을 재활용하는 느낌이 왔으면 시간 복잡도를 계산해 볼 차례이다.
[0, i-1]을 만족하는 k에 대해서 k + d[k]의 최댓값을 r이라 하고 이때의 k값을 p라고 하자. 위 그림으로 비교해보면 r = p + d[p]이다.

vector<int> manachers(string str){
  int N = str.size(), r = 0, p = 0;
  vector<int> d(N, 0);
  for (int i = 0; i < N; i++){
    if (i <= r) d[i] = min(d[2*p-i], r-i);
    while (i - d[i] - 1 >= 0 && i + d[i] + 1 < N 
      && str[i - d[i] - 1] == str[i + d[i] +1 ]) d[i]++;
    if (r < i + d[i]) {
      r = i + d[i];
      p = i;
    }
  }
  return d;
}

 

첫 번째 case, 두 번째 case의 두번째 경우에 해당될 때는 while문이 실행되고, 아래 r < i + d[i]가 만족해서 r은 더 커질 것이다.

두 번째 case의 첫 번째 경우에 해당된다면 d[i] = d[2*p-i] 만 수행되고 끝난다.

 

반복문이 얼마만큼 수행되는지 보면 시간 복잡도가 보인다.

밖에 있는 for문은 문자열의 길이만큼 수행이 될 거고$\ \cdots O(n)$,
안에 있는 while문은 누적해서 r만큼 수행이 되는데 r은 최대 N이다.$\ \cdots O(n)$

 

따라서 모든 위치에서의 최대 palindrome인 d[i]를 전부 구하는데 $O(n)$가 걸린다.

 

짝수 길이의 경우

한 가지 간과한 게 있는데 지금 구한 배열의 정의는 d[i] = i를 중심으로 가장 긴 palindrome의 길이(반지름)이다.
이렇게 하면 중심이 두 개인 짝수 길이의 palindrome은 놓치게 되는데, 이는 단순히 입력받은 문자열 사이에 임의의 문자열(예를 들어 '.')을 삽입하는 방법으로 해결할 수 있다.