반응형



목차


1. Manacher 알고리즘(Manacher's Algorithm)란?


2. manacher 알고리즘 동작 원리


3. manacher 알고리즘 접목


4. 관련 문제






1. Manacher 알고리즘(Manacher's Algorithm)란?


이번 포스팅에서는 Manacher 알고리즘(Manacher's Algorithm)에 대해 알아보고자 한다.


우선 manacher 알고리즘이 언제 쓰이고, 왜 쓰이는지 알아보자.


앞서 필자는 부분 문자열의 팰린드롬 판별 알고리즘에 대해 설명한 적이 있다.

http://www.crocus.co.kr/1001


위의 알고리즘은 O(n^2)이라는 시간 복잡도를 가지고 있어 n = 10000이 된다면 시간 복잡도가 1억이 된다.


따라서 10000이상의 길이를 가진 문자열의 부분 문자열에 대해서 팰린드롬 판단 빠르게 해줄 수 없다.


이를 위해 우리는 문자열의 부분 문자열이 팰린드롬인지 O(n)에 판단하는 manacher 알고리즘을 알아보고자 한다.


manacher 알고리즘의 시간 복잡도 :: O(n)





2. manacher 알고리즘 동작 원리


manacher 알고리즘을 이용하여 우선 문자열 S에 대한 배열 A를 구할 수 있다.


이때 배열 A는 다음과 같이 정의된다.


A배열 i번째 원소 A[i]는 i번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기를 의미한다.

예를들어 bananac에서 붉은색 a의 A[4]는 최대 반지름인 2가 된다.


즉, 부분 문자열 S의 4 - A[4]에서 4 + A[4]까지는 팰린드롬이며, 4 - A[4] - 1에서 4 + A[4] + 1까지는 팰린드롬 아니다.

(anana는 팰린드롬이지만, bananac는 팰린드롬이 아니다.)


이를 일반화 하면 어떤 문자열 S에서 A[i]가 존재한다면, 


i - A[i]에서 i + A[i]까지는 팰린드롬고, i - A[i] - 1에서 i + A[i] + 1까지는 팰린드롬이  아니라는 것이다.


이 과정을 이용하여 bananac라는 문자열에 대한 배열 A를 알아보자.


S

b

a

n

a

n

a

c

A

0

0

1

2

1

0

0



manacher 알고리즘 동작 원리는 다음과 같다.

1. i는 1부터 N(문자열의 길이)까지 진행된다.


2. j < i인 모든 j에 대해 r=max(j + A[j])이라 하고, 또한 그러한 j를 p라 하자. 즉, r=p + A[p]


3. i와 r의 대소 관계에 따라 A[i]의 초기값이 결정된다.

  1. i > r이라면, A[i]의 초기값은 0이다.

  2. i ≤ r이라면, i는 p를 중심으로 한 회문에 속한다. 따라서 그 회문에서 i의 대칭점을 i′라 하자. 즉, i′=2p - i가 된다.

     그리고 A[i]의 초기값은 min(r - i, A[i′])이다. (즉, r은 중심점 p를 기준으로 하는 p + A[p]를 의미하게 된다.)


4. A[i]의 초기값이 결정되고, S[i - A[i]]와 S[i + A[i]]가 같을 때까지 A[i]를 증가시킨다.




bananac는 위와 같이 형성됨을 알 수 있다.


각 인덱스에 대해 r이 의미해주는 것은 각 인덱스에 대해 팰린드롬이 될 수 있는 최대 범위를 말해주고 있고

p는 그러한 r이 형성되고 있는 중심점을 나타내주고 있다.


이 과정을 코드로 나타내면 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void manachers(string S, int N)
{
    int r = 0, p = 0;
    for (int i = 0; i < N; i++)
    {
        if (i <= r)
            A[i] = min(A[* p - i], r - i);
        else
            A[i] = 0;
 
        while (i - A[i] - >= && i + A[i] + < N && S[i - A[i] - 1== S[i + A[i] + 1])
            A[i]++;
        
        if (r < i + A[i])
        {
            r = i + A[i];
            p = i;
        }
    }
}
cs



이때 우리는 baaba라는 문자열이 존재 할 때 aa의 팰린드롬을 구할 수 없게 된다.

왜냐면 위의 코드로는 aab 혹은 baa같은 문자열 밖에 확인 하지 못하기 때문이다.


따라서 우리는 저러한 짝수 부분 문자열의 팰린드롬을 구하기 위해 


#b#a#a#b#a#로 문자를 치환해준다면 a#a에서 #을 이용하여 팰린드롬을 구할 수 있다.










3. manacher 알고리즘 접목


가장 대표적인 예제 문제를 하나 풀어보자.


[14444번] 가장 긴 팰린드롬 :: https://www.acmicpc.net/problem/14444


이 문제는 위의 O(n^2)의 부분 문자열의 팰린드롬 판별 알고리즘으로 해결 할 수 없다.

http://www.crocus.co.kr/1001


이제 manacher 알고리즘을 접목해보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
 
using namespace std;
 
const int MAXN = 100001 * 2;
 
string tmp, str;
 
int A[MAXN];
 
void manachers(string S, int N)
{
    int r = 0, p = 0;
    for (int i = 0; i < N; i++)
    {
        if (i <= r)
            A[i] = min(A[* p - i], r - i);
        else
            A[i] = 0;
 
        while (i - A[i] - >= && i + A[i] + < N && S[i - A[i] - 1== S[i + A[i] + 1])
            A[i]++;
 
        if (r < i + A[i])
        {
            r = i + A[i];
            p = i;
        }
    }
}
int main()
{
    cin >> tmp;
 
    int len = tmp.size();
 
    for (int i = 0; i < len; i++)
    {
        str += '#';
        str += tmp[i];
    }
    str += '#';
 
    manachers(str, str.size());
 
    len = str.size();
    int ans = -1;
    for (int i = 0; i < len; i++)
        ans = max(ans, A[i]);
 
    printf("%d", ans);
 
    return 0;
}
cs


bananac를 보면


#b#a#n#a#n#a#c가 된다.


이때 #b#a#n#a#n#a#c에서 a 기준으로 A[8]은 5가 될 것이다.


#을 추가함으로써 붉은색 a에서의 최종 팰린드롬 길이가 5가 됨도 파악 할 수 있다.(anana)

그 이유는 a를 기준으로 왼쪽에 오른쪽의 ac가 #으로 대체되기 때문이다.




4. 관련 문제


http://www.crocus.co.kr/search/manacher


반응형