Manacher's Algorithm (팰린드롬, 회문 구하기)

Manacher's Algorithm은 문자열 내에서 회문(팰린드롬, palindrome)을 찾는 것과 관련된 알고리즘이며, 시간복잡도는 O(N)이다. (여기서 N은 문자열의 길이)

 

여기서 회문, 팰린드롬이란, 앞뒤를 뒤집어도 똑같은 문자열을 의미한다.

 

여기서 단순하게 하나하나 문자열을 자르고 뒤집어 비교하는 것은 시간이 오래 걸리기에 효율적이지 못하다.

 

이 알고리즘은 문자열 S에 대해 다음과 같은 배열을 만들 수 있다.

• 문자열 S의 길이를 N이라 하고 (|S| = N) 같은 길이의 정수 배열 A를 만든다.

• A의 i번째 원소 A[i]는 i번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기이다. (회문의 길이가 5이면, 반지름은 2가 된다)

• 즉, 부분 문자열 S[i-A[i] , i+A[i]] 는 회문이며 S[i-A[i]-1 , i+A[i]+1] 은 회문이 아니다.

 

예를 들어 "banana"라는 문자열 S에 대한 배열 A는 다음과 같다. 

S	b	a	n	a	n	a
A	0	0	1	2	1	0

알고리즘은 다음과 같다.

1. i 는 1부터 N ( N=|S| )까지 진행된다.

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

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

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

• i ≤ r 이라면, i 는 p 를 중심으로 한 회문에 속한다. 따라서 그 회문에서 i 의 대칭점을 i′ 라 하자. 즉, i′ = 2p−i 그리고 A[i] 의 초기값은 min( r−i,A[i′] )이다.

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

의사코드로 구현하면 다음과 같다

R = -1 p = -1 for i = 0 to n-1:     if i <= R:  A[i] = min(A[2*p - i], R-i)     else:  A[i] = 0     while S[i-A[i]-1] == S[i+A[i]+1]:         A[i] = A[i] + 1     if i+A[i] > R:         R = i+A[i], p = i

시간복잡도 분석

나올 수 있는 A[i] 의 초기값은 3가지이다.

우선, A[i] 의 초기값이 A[i′] 인 경우, A[i] 의 값이 더이상 증가하지 않는다. 즉, while 문을 돌지 않는다. A[i′] 값이 결정되었다는 것은, S[ i′−A[i′]−1 ] 과 S[ i′+A[i′]+1 ] 가 다르다는 것인데, 조건에 따라 S[ i′−A[i′]−1 ] = S[ i+A[i′]+1 ]이고, S[ i′+A[i′]+1 ] = S[ i−A[i′]−1 ] 이다. 따라서,S[ i−A[i′]−1 ]과 S[ i+A[i′]+1 ]은 다르다.

나머지 두 경우에 대해서는, i + A[i] ≥ r 이라는 것이다. 이 때, r 값은 while문 도는 회수 만큼 증가하게 된다. 그런데 r 값은 정의에 따라 절대 감소하지 않으므로, while 문은 총 N번 돈다는 것을 알 수 있다. 따라서 전체 시간복잡도는 O(N)이다.

 

모든 회문 구하기

이 알고리즘에서 특정 문자를 중심으로 한 회문만을 취급하기 때문에 짝수 길이의 회문을 고려할 수 없다. 짝수 길이의 회문을 구할 때에는 기존 문자열 S의 각 문자 사이에 '#'를 추가하면 된다. 예를 들어, "abccba"라는 회문은 "a#b#c#c#b#a"가 되어 길이가 홀수가 된다.

 

출처: Algospot.com Wiki