shjgkwo's profile image

shjgkwo

March 10, 2019 23:30

Manacher's Algorithm

algorithm , palindrome

목차

개요

이 포스트를 쓰며

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

팰린드롬

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

간단한 원리

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

기본

일단 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

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

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

사진1

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

구현

위의 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

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

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

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

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

문제풀이

팰린드롬

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

#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

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

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

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

#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

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

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

즉, 열, 을 고정해 놓고 그것을 거대한 문자열이라고 보고 manacher를 실행하는 문제로 바뀌게 된다! 따라서 이 경우에 시간복잡도는 이다.

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

#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한 것을 찾는 문제이다.

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

먼저 으로, 즉, 반절 씩 쪼갠뒤, 짝수 번째엔 홀수 번째엔 를 차례로 넣는다고 하자. 이때 조심해야할것이 suffix 이므로 는 뒤집어서 넣어준다고 하자.

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

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

#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 를 준비하는 모든 사람에게 도움이 되었으면 좋겠다.

참고자료