shjgkwo's profile image

shjgkwo

March 10, 2019 23:30

Manacher's Algorithm

algorithm , palindrome

목차

개요

이 포스트를 쓰며

학기가 시작되어 모든 알고리즘들을 한번씩 보면서 넘어가던 도중 사람들이 잘 관심 가지지 않지만, 알아두면 재미있을법한 알고리즘인 Manacher’s Algorithm 을 소개해보고자 한다. Manacher’s Algorithm은 String 내에 존재하는 모든 Palindrome을 \(O(N)\)에 구하는 강력한 알고리즘이다. 물론 이 알고리즘이 실전에 출제되는 경우는 매우 드물지만 원리 자체가 재미있고 시간복잡도가 \(O(N)\)이 되는 원리가 재미있는 알고리즘이므로 자세하게 설명해보고자 한다.

팰린드롬

팰린드롬을 모르는 사람을 위해 간단히 설명하자면 앞에서 읽으나 뒤에서 읽으나 항상 똑같이 읽어지는 문자열을 의미한다. 예를 들어, “여보안경안보여” 는 팰린드롬이다. 거꾸로 읽으나 제대로 읽으나 “여보안경안보여”이다. 물론, 한국어로 문제를 내는 경향은 드무니, 알파벳 기준으로 설명한다면, “ababa”등이 있을 것이다. 이러한 거꾸로 읽으나 제대로 읽으나 항상 같은 문자열을 팰린드롬이라 하며, 더 엄밀한 정의로는 문자열의 길이를 \(n\)이라고 하고 \(0\) 부터 \(n-1\)까지 각 문자열에 해당하는 문자에 번호를 매긴다면, (이를테면 “branch” 에서 0번째는 ‘b’ 고 4번째는 ‘c’가 된다), \(i\)번째 문자 와 \(n-i-1\) 번째 문자가 같은 문자열을 의미한다.

간단한 원리

우선 간단한 반복문, 배열만 사용할 줄 알면 되는 매우 간단하고 이해하기도 쉬운 알고리즘이다. 단, 다이나믹 프로그래밍에 대한 약간의 지식이 있으면 도움 이 될것이다. 일단 부분 문자열(주어진 문자열에서 연속되는 맨 앞에서 부터 \(k\)개, 뒤에서 부터 \(l\)개(\(k + l < n\))를 자른 문자열)중에 팰린 드롬이 되는 제일 긴 문자열을 찾고, 그 문자열의 중심으로 부터 대칭되는 부분 문자열 역시 팰린드롬이다 라는 아이디어에서 출발하는 알고리즘이다. 그리고 그것을 이용하여 모든 팰린드롬을 구한다.

기본

일단 pseudo code는 다음과 같다.

s = input string
p = [radius of palindrome]

r = -1  # end of palindrome
c = -1  # center of palindrome

for i in range(0, n - 1)
    if r >= i
        p[i] = min(r - i, p[c * 2 - i])  # c + (c - i) symmetric point
    else
        p[i] = 0
    
    while i + p[i] + 1 < n
        if s[i + p[i] + 1] == s[i - p[i] - 1]
            p[i] += 1
        else
            break
    
    if i + p[i] > r
        r = i + p[i]
        c = i

\(s\)는 입력으로 주어지는 문자열을 의미한다. \(p\)는 배열으로서 현재위치에서의 팰린드롬의 반경을 의미한다. 즉 “abcba” 가 있다고 한다면 \(c\)에 해당하는 반경은 \(2\)가 된다. 이때, \(p[i] * 2 + 1\)을 하면 그 팰린드롬에 해당하는 부분 문자열의 최대 길이를 알 수 있다. \(r\) 은 위의 기본 원리에서 설명했던 부분 문자열의 끝을 의미한다. \(c\)는 그 부분문자열의 중앙을 의미한다.

이제 여기서 for 에서 \(r\), 즉, 부분 문자열의 끝보다 \(i\)가 작으면 그 부분문자열에 대칭하는 지점에 해당하는 \(p\)값을 가져온 뒤, \(r - i\), 즉, 끝 지점과 현재 \(i\)와의 거리를 구해서 둘 중 작은 쪽으로 넣어준다. 이렇게 하는 이유는 대칭되는 지점이 팰린드롬이 해당 부분문자열을 벗어나는 지점에 있다면, 그것이 현재 \(i\)가 똑같으리라는 보장이 없기 때문이다. 자세한건 그림을 통해 확인해보자.

사진1

위에 사진에서 “abababa” 에 앞에는 “abab”를 추가로, 뒤에는 “cbcb”를 추가로 넣는다고 해보자. 뒤에 만약을 가정하여, 가장 마지막 문자열의 대칭 지점과 원래 지점에서 는 bab로 인하여 실제로 \(p[c * 2 - i]\)는 더 길것이다. 하지만 \(p[i]\)는 절대로 그것보다 길게 나올 수 없다. 이것 때문에 \(r - i\)와 \(p[c * 2 - i]\)를 비교하는 것이다.

구현

위의 pseudo code 를 C++로 구현한 코드이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
 
#define MAXN 100001
 
using namespace std;
 
int p[MAXN]; // 팰린드롬의 반경
char o[MAXN]; // 문자열
int main() {
	int i;
	int n; // 문자열의 길이
	int r, c; // 맨 끝의 위치, 중간의 위치
	r = c = -1;
	scanf("%s",o);
	n = strlen(o);
 
	// even palindrome
	for (i = n - 1; i >= 0; i--) {
		o[(i << 1)+1] = o[i];
		o[i << 1] = '#';
	}
	n <<= 1;
	o[n++] = '#';
 
	for (i = 0; i < n; i++) {
		if (r >= i) p[i] = min(r - i, p[c * 2 - i]); // 작은 쪽을 넣어준다.
		else p[i] = 0;
 
		while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && o[i + p[i] + 1] == o[i - p[i] - 1]) p[i]++; // 같으면 증가
		if (i + p[i] > r) { // 끝지점을 넘어서면 그때마다 갱신
			r = i + p[i];
			c = i;
		}
	}
 
	for(i=0;i<n;i++) printf("%d ",p[i]);
	return 0;
}

먼저 살펴볼 수 있는 것은 even palindrome 으로 주석처리된 부분인데, 이는 짝수 팰린드롬의 처리를 의미한다. 위에서 홀수 팰린드롬만을 설명했었다. 그렇다면 짝수 팰린드롬은 어떻게 처리할까?

사진2

위 그림에서 보다 싶이 문자열의 각 \(i\)번째 문자들을 \(2i + 1\)번째로 옮긴 뒤, 첫번째와 맨 마지막, 그리고 사이사이 남는 공간에 ‘#’ 문자를 끼워주는 방법이다. 이렇게 하면, linear한 추가 공간과 시간을 사용하여 짝수 팰린드롬 또한 찾을 수 있게 된다.

그렇게 되어서 위 코드에서 ‘#’을 채워주는 것이다. 구현은 이렇게 간단하다.

그렇다면 시간복잡도는 어떻게 \(O(N)\)이 되는것일까? 그 비밀은 while에 숨겨져있다. 얼핏 보면 \(O(N^{2})\) 처럼 보이지만, while은 실제로 linear하게 동작한다. 그 이유는, \(p[i]\)가 증가하려면 \(r\)에 변화가 있다는 뜻이다. \(r\)에 변화가 없다는건, 대칭되는 \(p[c * 2 - i]\)가 \(r\)보다 작은 경우여서, \(p[i]\)가 증가할 이유가 없기 때문이다. 혹은, 정확히 r에 도달할 수 도 있다. 이 경우에도 마찬가지로 대칭되는 지점과 공유하므로 \(p[i]\)가 증가할 일은 없다. 그런데 \(r\)은 감소할 일이 없는 변수이다. 즉, 증가하기만 하고 감소할 일은 없으니 while이 도는 횟수는 결국 전체 합쳐서 \(n\)보다 클수가 없다. 따라서, 시간복잡도는 \(O(N)\)이 된다. 전에 있던 p를 사용하여 그 다음 p를 결정하는건 약간 다이나믹 프로그래밍과 비슷한 아이디어지만 대칭성을 이용하는 아름다운 알고리즘이 된다.

이제 문제를 풀어보도록 하자.

문제풀이

팰린드롬

링크를 통하여 문제를 확인해 볼 수 있다. 너무나 당당하게 팰린드롬이라 적힌 문제이다. 이 문제는 각 문자들을 팰린드롬으로 잘게 쪼갰을 때 그 개수를 최소화 하는 문제이다. 그렇다면 가장 먼저 떠오르는 방법이 무엇일까? 그렇다 바로 DP 이다. 현재 위치를 \(i\) 라고 한다면 \(table[i]=min(table[j]+1) (j < i)\)의 점화식으로 구해내는 것이다. 이때 \([j + 1, i]\)구간의 문자열이 팰린드롬인지만 확인하면 되고 \(table[j]\)가 가능한 숫자인지만 검증하면 된다. 자, 우선 \(table[j]\)가 가능한 숫자인것을 검증하는 것은 매우 쉬운 일이다. 하지만, 특정 구간의 문자열이 팰린드롬이라는걸 확신하는 방법은? 그렇다 manacher를 이용하면 된다. 아래 코드는 \(p\)의 범위를 활용하여 \(p[i]\)에 대해 \(table[i+j]\)를 \(table[i-j]\)로 갱신하는 방법을 택했다. 이 경우엔 굳이 검증작업이 필요가 없다.

#include <stdio.h>
#include <string.h>

int n;
int p[4010];
int table[4010];
char o[4010];

void manacher() {
	int i;
	int c = -1;
	int k;
	for(i=0;i<n;i++) {
		if(c == -1) k = 0;
		else k = p[2*c-i] <= c+p[c]-i ? p[2*c-i] : c+p[c]-i; // r을 사용하지 않고 대신 c + p[c]를 활용하였다.

		while(i-k-1 >= 0 && i+k+1 < n && o[i-k-1] == o[i+k+1]) k++;
		if(i+k > c+p[c]) c = i;
		p[i] = k;
	}
}

int main() {
	int i;
	int k1;
	scanf("%s",o);
	n = strlen(o);
	for(i=n-1;i>=0;i--) {
		o[i*2+1] = o[i];
		o[i*2] = '#';
	}
	n *= 2;
	o[n++] = '#';
	manacher();
	int j;
	for(i=0;i<n;i++) table[i] = 100000000;
	table[0] = table[1] = table[2] = 1;
	for(i=0;i<n;i++) {
		for(j=p[i];j>=0;j--) {
			if(i-j == 0) table[i+j] = 1;
			k1 = 0x7fffffff;
			if(o[i-j] == '#') {
				k1 = table[i-j];
				if(i-j-1 >= 0 && k1 > table[i-j-1]) k1 = table[i-j-1];

				if(k1 + 1 < table[i+j]) table[i+j] = k1 + 1;
			}
			else {
				if(i-j-1 >= 0) k1 = table[i-j-1];
				if(i-j-2 >= 0 && k1 > table[i-j-2]) k1 = table[i-j-2];

				if(k1 + 1 < table[i+j]) table[i+j] = k1 + 1;
			}
		}
	}
	printf("%d",table[n-1]);
	return 0;
}

Casting Spells

링크를 통하여 문제를 확인할 수 있다. 이 문제는 주문을 외우는 데 주문에는 각각의 힘이 있다고 한다. 그 힘이란 어떤 임의의 문자열 \(w\)가 있다고 가정했을 때, \(ww^{R}ww^{R}\)이 입력으로 주어지는 문자열 내부에 존재한다고 하자. 이때 \(ww^{R}ww^{R}\) 의 길이가 제일 긴 것이 그 주문의 힘이라고 한다. (\(w^{R}\)은 뒤집기)

이 문제는 바로 눈치챘겠지만, 짝수 팰린드롬 두개를 이어붙여서 또 팰린드롬이 나오는지 확인하는 문제이다. 그렇다면 짝수 팰린드롬 두개를 이어붙여서 제일 긴 팰린드롬을 찾는건 어떻게 할까? 그것은 간단하다. plane sweep 아이디어를 이용하는 것이다. 우선 \(ww^{R}ww^{R}\) 을 찾고 \(ww^{R}\) 가 되어줄 다른 팰린드롬이 있는지 \(i\) 를 늘려나가면서 찾는 것이다. 먼저 \(i\)를 \(set\)에 집어넣고, \(i + p[i]\) 지점에 그 \(i\)를 다시 지우는 것이다. 그런식으로 넣고 지워가면서 어떤 지점 \(i\)에 대해서 \(\frac{i - p[i]}{2}\) 의 lower bound 를 찾고 그 지점에 해당하는 i가 존재하는지 찾으면 되는것이다. 이때의 시간복잡도는 \(O(N log N)\) 이 된다.

아래는 위 풀이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int p[600010];
char o[600010];
set<int> st;

vector<int> right[600010];

int main() {
    int z;
    scanf("%d", &z);
    while(z--) {
        int n;
        scanf("%s", o);
        n = (int)strlen(o);
        for(int i = n - 1; i >= 0; i--) {
            o[i * 2 + 1] = o[i];
            o[i * 2] = '#';
        }
        o[n * 2] = '#';
        n = n * 2 + 1;
        o[n] = '\0';
        
        int r;
        int c = r = -1;
        for(int i = 0; i < n; i++) { // 일단 manacher로 반경을 모두 구해놓고 시작한다.
            if(r >= i) p[i] = min(p[c * 2 - i], r - i);
            else p[i] = 0;
            while(i + p[i] + 1 < n && i - p[i] - 1 >= 0 && o[i + p[i] + 1] == o[i - p[i] - 1]) p[i]++;
            if(i + p[i] > r) {
                r = i + p[i];
                c = i;
            }
        }
        
        for(int i = 0; i < n; i += 2) {
            right[i].push_back(i + 1); // 현재 지점
            right[i + p[i]].push_back(-i - 1); // 길이의 한계, 즉 삭제되는 시점
        }
        
        int ans = 0;
        
        for(int i = 0; i < n; i += 2) {
            // 발견되는 시점으로 set에 넣어준다.
            for(int j = 0; j < right[i].size(); j++) if(right[i][j] > 0) st.insert(right[i][j] - 1);

            //해당 길이를 포함하는 짝수 팰린드롬이 존재하는지, 그것도 가장 긴것으로 찾는다.
            set<int>::iterator it = st.lower_bound(i - p[i] / 2);
            if(it != st.end() && st.size()) {
                ans = max(ans, (i - *it) * 2);
            }

            // 삭제되는 시점이므로 삭제해준다.
            for(int j = 0; j < right[i].size(); j++) if(right[i][j] < 0) st.erase(-right[i][j] - 1);
        }
        st.clear();
        
        printf("%d\n",ans);
        
        
        for(int i = 0; i < n; i++) {
            p[i] = 0;
            right[i].clear();
        }
    }
    return 0;
}

Sonya and Matrix Beauty

링크를 통하여 문제를 확인할 수 있다. 이 문제는 \(n \times m\) 행렬에서 한 행에 들어있는 문자들을 모두 재배열 할 수 있을때(이러한 작업을 모든 행에서 수행 가능)재배열 하고 난뒤, \(i_{1}, j_{1}, i_{2}, j_{2}\) 네 좌표로 만들 수 있는 사각형에서 모든 행과 열이 팰린드롬이 되는지 확인하는 문제이다. 그리고 그러한 네 좌표들의 모든 경우의 수를 출력하는 문제이다.

일단, 가장 먼저 DP를 사용하여 알파벳 성분들을 모두 구해서 행이 고정 되었을때, \(j_{1}, j_{2}\)의 알파벳 성분들을 26개로 구해서 하나의 거대한 알파벳이라고 생각하는 것이다. 그러면 하나의 거대한 문자열이 만들어지는것을 확인 할 수 있다. 여기서 더 나아가서 26개의 성분들이 전부 짝수이거나, 혹은 단 한개만 홀수이고 나머지는 짝수인경우 행에 대해서 팰린드롬을 만들 수 있다는 사실도 알 수 있다.

즉, 열, \(j_{1}, j_{2}\) 을 고정해 놓고 그것을 거대한 문자열이라고 보고 manacher를 실행하는 문제로 바뀌게 된다! 따라서 이 경우에 시간복잡도는 \(O(nm^{2})\) 이다.

아래는 위 풀이를 구현한 코드이다.

#include <cstdio>
#include <algorithm>

using namespace std;

char o[520][520];
int cnt[520][31];
int impossible[520];
int tr[128];

int p[520];

bool equal(int x, int y) { // 두 성분을 비교
    if(impossible[x] || impossible[y]) return false; //불가능 할때는 무조건 거짓을 반환
    for(int i = 0; i < 27; i++) {
        if(cnt[x][i] != cnt[y][i]) return false; // 성분이 다른게 하나라도 있으면 거짓을 반환
    }
    return true; // 참
}

int main() {
    for(int i = 'a'; i <= 'z'; i++) tr[i] = i - 'a';
    tr['z' + 1] = 'z' + 1 - 'a';
    
    int n, m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n * 2; i += 2) {
        scanf("%s",o[i]);
        for(int j = 0; j < m; j++) o[i - 1][j] = 'z' + 1;
    }
    for(int i = 0; i < m; i++) o[n * 2][i] = 'z' + 1;
    
    n *= 2;
    n++;
    
    long long ans = 0;
    for(int i = 0; i < m; i++) {
        
        for(int j = 0; j < n; j++) for(int k = 0; k < 27; k++) cnt[j][k] = 0;
        
        for(int j = i; j < m; j++) {
            for(int k = 0; k < n; k++) {
                cnt[k][tr[o[k][j]]]++;
                
                int flag = 0;
                for(int l = 0; l < 27; l++) if(cnt[k][l] & 1) flag++;
                
                if((flag == 1 && (j - i) % 2 == 0) || flag == 0) impossible[k] = 0;
                else impossible[k] = 1;
                
                p[k] = 0;
            }
            
            int r, c;
            r = c = -1;
            for (int k = 0; k < n; k++) {
                if (r >= k) p[k] = min(r - k, p[c * 2 - k]);
                else p[k] = 0;
                
                // 성분을 거대한 알파벳으로 보고 manacher's algorithm을 돌린다.
                while (k + p[k] + 1 < n && k - p[k] - 1 >= 0 && equal(k + p[k] + 1, k - p[k] - 1)) p[k]++;
                if (k + p[k] > r) {
                    r = k + p[k];
                    c = k;
                }
            }
            for(int k = 0; k < n; k++) { // 직후 그 값을 더해준다.
                if((k & 1) && !impossible[k]) {
                    ans += (p[k] + 1) / 2;
                }
                if(!(k & 1)) {
                    ans += p[k] / 2;
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Prefixuffix

링크를 통하여 문제를 확인할 수 있다. 이 문제는 cyclically equivalent 한 prefix와 suffix를 찾는것인데, 일단 cyclically equivalent가 무엇이냐면, “abbaab” 와 “abaabba” 같이 한 문자열을 회전 시킬때 마다, 즉 맨 앞에 있는 문자를 뒤로 보내거나, 맨 뒤에 있는 문자를 맨 앞으로 보내는 행위를 여러번해서 동일하게 만들 수 있는 문자열을 cyclically equivalent 하다고 한다. 이때 주어진 문자열의 prefix와 suffix중에 cyclically equivalent한 것을 찾는 문제이다.

먼저 생각해볼 수 있는 것은 \(O(N^{2})\) 풀이로서 그냥 맨 앞부터 for를 돌리면서 맨 뒤에서 \([n-i-1, n-1]\) 범위와 \([0, i]\) 를 비교하는 것이다. 당연하게도 이 방법은 개선할 여지가 단 하나도 없다. 그렇다면 이 문제를 해결하려면 무슨 방법을 써야할까? 그것은 단어를 섞는것이다. 일단 홀수의 경우 가운데 문자열은 항상 안쓰게 되니 제거하여 짝수 문자열의 경우만 생각해보자.

먼저 \(\frac{n}{2}\) 으로, 즉, 반절 씩 쪼갠뒤, 짝수 번째엔 \([0, \frac{n}{2} - 1]\) 홀수 번째엔 \([\frac{n}{2}, n - 1]\)를 차례로 넣는다고 하자. 이때 조심해야할것이 suffix 이므로 \([\frac{n}{2}, n - 1]\)는 뒤집어서 넣어준다고 하자.

이렇게 되면, \(s_{0} s_{n-1} s_{1} s_{n-2} s_{2} s_{n-3} s_{3} s_{n-4} ...\) 이런식으로 반복되어서 들어가게 되는데 여기서 여기서 \(s_{0}\) 부터 시작하는 팰린드롬을 구하게 되면 그것이 prefix 와 suffix가 같은 경우임을 알 수 있다. (직접 증명해보자.) 그러면 남은것은 무엇일까? cyclically equivalent 한것을 찾는것이 우리 최초 목표였는데 그 목표는 의외로 쉽게 풀린다. 다시 재조립된 문자열을 \(S\) 라고 하자. \(S\) 에서 시작지점을 포함한 팰린드롬과 그 팰린드롬과 맞닿는 지점에서 시작하는 팰린드롬 두개를 구해서 합친것중 제일 긴것을 구하는 문제로 변형할 수 있다! 이는 set을 이용하여 매우 간단하게 구할 수 있으니 manacher와 set을 적당히 조합해서 해결하면 된다. 이때의 시간복잡도는 \(O(N log N)\)

아래는 위 풀이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

#define MAXN 2000100

using namespace std;

int p[MAXN];
char o[MAXN];
char u[MAXN];

set<int> pre;

int main() {
    int n;
    int r, c;
    r = c = -1;
    scanf("%d",&n);
    scanf("%s",u);
    if(n == 1) {
        printf("0\n");
        return 0;
    }
    if(n & 1) { // 홀수인 경우 가운데 문자는 쓸모가 없다. 제거한다.
        for(int i = n / 2; i < n - 1; i++) u[i] = u[i + 1];
        u[n - 1] = '\0';
        n--;
    }
    reverse(u + n / 2, u + n); // 뒤집어준다.
    int x = 0, y = n / 2;
    for(int i = 0; i < n; i++) { // 섞는다.
        if(i & 1) o[i] = u[y++];
        else o[i] = u[x++];
    }
    
    for (int i = n - 1; i >= 0; i--) {
        o[(i << 1)+1] = o[i];
        o[i << 1] = '#';
    }
    n <<= 1;
    o[n++] = '#';
    
    for (int i = 0; i < n; i++) {
        if (r >= i) p[i] = min(r - i, p[c * 2 - i]);
        else p[i] = 0;
        
        while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 && o[i + p[i] + 1] == o[i - p[i] - 1]) p[i]++;
        if (i + p[i] > r) {
            r = i + p[i];
            c = i;
        }
    }
    
    int ans = 0;
    
    pre.insert(0);
    
    for(int i = 0; i < n; i += 2) { // 팰린드롬 두개를 엮어서 제일 긴 문자열을 만드는지 확인한다.
        set<int>::iterator it = pre.lower_bound(i - p[i]);
        if(*it >= i - p[i]) {
            int tmp = *it - (i - p[i]);
            tmp = p[i] - tmp;
            if(ans < i + tmp) ans = i + tmp;
        }
        if(i - p[i] == 0) pre.insert(i + p[i]);
    }
    printf("%d\n",ans / 4);
    return 0;
}

마무리

이 포스트를 통해 문자열 알고리즘, 그중에서도 Palindrome 문제를 manacher 알고리즘을 통하여 해결하는 다수의 문제를 보았다. 매우 지엽적인 알고리즘인 만큼 출제가 잘 되는 편은 아니지만, 활용도가 매우 높고, 문제 만드는 입장에서는 온갖 테크닉으로 상대방을 괴롭힐 수 있는 알고리즘이므로 꼭 알아두면 좋겠다 싶어서 이렇게 리뷰해 보았다. 이를 통해 CP 를 준비하는 모든 사람에게 도움이 되었으면 좋겠다.

참고자료