매내처 알고리즘(Manacher's algorithm)

우린 다음과 같은 문제를 해결한다고 해보자.

 

어떤 문자열의 부분 문자열 중 팰린드롬인 것의 개수를 구하기.

 

흔히들 배우는 방법으로는 $O(N^{2})$에 해결할 수 있는 동적 계획법이 있다.

 

하지만 N이 10000을 넘어간다면 메모리와 시간에 상당한 제약을 받게 될 것이다.

 

매내처 알고리즘은 선형 시간 복잡도 $O(N)$에 풀 수 있는 해법을 제시한다.

 

중요 아이디어는 다음과 같다.

 

과정은 뒤로 미뤄두고 우리는 탐색하고 있는 인덱스 i의 이전에 존재하면서 마지막 인덱스 j가 j > i인 팰린드롬을 구했다고 하자.

 

그리고 이 팰린드롬이 커버하고 있는 범위는 현재 인덱스 i를 포함하여 더 넓게 차지하고 있는 상황이다.

 

그러면 그 팰린드롬의 중심을 기준으로 양 옆에는 서로 같은 자식 팰린드롬이 있을 수 있다.

 

abacaba로 예시를 들어보자.

 

a

b

a

c

a

b

a

 

딱 봐도 팰린드롬이다. 양 옆을 보면

 

a

b

a

c

a

b

a

 

위와 같이 aba라는 서로 같은 자식 팰린드롬이 기준점 c를 중심으로 위치함을 확인할 수 있다.

 

매내처 알고리즘은 현재 탐색하고 있는 인덱스 i를 어떤 자식 팰린드롬이라 생각하고 건너편 자식 팰린드롬의 반지름을 취함으로써 속도를 개선한다.

 

위의 예제의 경우에는 자식 팰린드롬의 길이가 2이므로 반지름이 3 이상인 팰린드롬부터 확인하게 된다.

 

그리고 이 계산 중 현재 인덱스 i를 넘는 팰린드롬을 찾았으면 위에 언급한 "탐색하고 있는 인덱스 i의 이전에 존재하면서 마지막 인덱스 j가 j > i인 팰린드롬"을 갱신해서 다음 인덱스에도 자식 팰린드롬을 찾을 수 있도록 해준다.

 

매내처 알고리즘은 이런 식으로 불필요한 계산을 생략하면서 팰린드롬이 몇 개나 출현하는지 아주 빠르게 센다.

구현

아이디어에 대해 알았으니 구현에 들어가 보자. 다만, 짝수 팰린드롬을 고려하는 전처리를 먼저 해야 한다.

 

위에 언급한 방법은 특정 인덱스를 기준으로 잡고 검색하는 것이라 당연히 홀수 팰린드롬에서만 적용할 수 있다. 짝수 팰린드롬도 검출하기 위해서는 더미 기준점을 하나 만들어야 한다.

 

더미 기준점은 쉽게 말해 문자 양 옆에 더미 문자를 배치하는 거다. 예를 들면 이렇게 되겠다.

 

aaaa -> #a#a#a#a#

 

이런 식으로 더미 문자를 끼워 넣으면 짝수 팰린드롬의 경우 #을 기준점으로 해서 탐색이 가능하기 때문에 딱히 전용 구현을 신경 쓸 필요가 없다.

 

다르게 말하면 매내처 알고리즘을 정상적으로 구현하려면 대상 문자열을 강제로 2배로 늘려야 한다는 소리가 된다.

 

그래도 대부분의 프로그래밍 대회 환경에서는 큰 문제가 되지 않을 것이다.

 

string ss("");

for (char cc : s)
{
  ss.push_back('#');
  ss.push_back(cc);
}
ss.push_back('#');

 

문자열을 전처리했으면 매내처 알고리즘을 구현해보자. 우선 변수 두 개가 필요하다. 이전 팰린드롬의 중심점을 나타내는 c와 반지름인 r이 그것이다. 이 둘은 처음에 -1로 초기화를 한다.

 

그리고 각 인덱스에서 최대 팰린드롬 반지름을 저장할 배열도 배치해야 한다.

 

int mana[4000005];
int r = -1;
int c = -1;

 

이 포스트에서는 mana라는 이름을 뒀다. mana 배열의 크기는 문자열 길이 * 2 + 2 임을 유의하라.(처음과 끝에 더미 문자를 넣으므로)

 

필요한 변수가 모두 준비되었으니 인덱스 i = 0부터 반복문을 타보자.

자식 팰린드롬 취하기

가장 먼저 언급한 중요 아이디어인 자식 팰린드롬의 반지름을 가져오자. $i \leq r$이여야 하는 건 너무나도 당연하다. 그러면 mana[i]에 들어갈 수 있는 값은 $min(r - i, mana[c + (c - i)])$가 된다.

 

r - i는 자식 팰린드롬이 가질 수 있는 반지름의 최대 크기이고, mana[c + (c - i)]는 건너편 자식 팰린드롬이 가지는 최대 팰린드롬 반지름 값이 된다.

 

mana[c + (c - i)]만 해도 되는 거 아닌가요?라는 물음이 있을 수 있는데 $mana[c + (c - i)] > r -  i$인 경우가 있을 수 있음을 명심하자.

 

if (i <= r)
{
  mana[i] = min(r - i, mana[c + (c - i)]);
}

팰린드롬 반지름 갱신

아무튼 이렇게 mana[i]의 값을 가져왔으면 (물론 조건을 만족하지 않으면 mana[i]는 당연히 0이다.) mana[i] 값을 늘려가면서 팰린드롬 검사를 실시하면 된다.

 

while (i + mana[i] + 1 < ss.size() and i - mana[i] - 1 >= 0 and ss[i + mana[i] + 1] == ss[i - mana[i] - 1])
{
  ++mana[i];
}

r과 c 갱신

그리고 i + mana[i] > r이 되면 r과 c를 갱신하여 다음 인덱스에서도 자식 팰린드롬을 찾을 수 있게 해주자.

 

if (i + mana[i] > r)
{
  c = i;
  r = i + mana[i];
}

최종

전체 코드로 나타내면 다음과 같은 모양이 될 것이다.

 

string s;
string ss;
int mana[4000005];
int r = -1;
int c = -1;

void solve()
{
  cin >> s;
  for (char cc : s)
  {
    ss.push_back('#');
    ss.push_back(cc);
  }
  ss.push_back('#');

  for (int i = 0; i < ss.size(); i++)
  {
    if (i <= r)
    {
      mana[i] = min(r - i, mana[c + (c - i)]);
    }

    while (i + mana[i] + 1 < ss.size() and i - mana[i] - 1 >= 0 and ss[i + mana[i] + 1] == ss[i - mana[i] - 1])
    {
      ++mana[i];
    }

    if (i + mana[i] > r)
    {
      c = i;
      r = i + mana[i];
    }
  }
}

 

이렇게 mana 배열에는 각 인덱스에 대해 최대 팰린드롬의 반지름이 저장된다. 그러면 이제 문제를 풀어보자.

 

https://www.acmicpc.net/problem/16163

16163번: #15164번_제보

 

매내처 알고리즘을 그대로 사용하면 되는 문제다. 매내처를 통해 모든 팰린드롬의 반지름을 구한 후 더미 문자들이 끼워져 있다는 사실을 고려하여 sum((반지름 + 1) / 2)를 계산하면 그것이 곧 팰린드롬의 갯수가 된다.

 

https://www.acmicpc.net/problem/14444

14444번: 가장 긴 팰린드롬 부분 문자열

 

이것도 그냥 시키는 대로 하면 된다.

 

매내처 알고리즘은 용도가 팰린드롬에 국한되어 있어 범용성은 떨어지지만 은근히 많은 문제가 백준에 있으니 익혀두면 큰 도움이 될 것이다.