Manacher's Algorithm

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

이 알고리즘은 문자열 $S$에 대해 아래와 같은 배열을 구할 수 있다.

• 문자열 $S$의 길이, $|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 \leq 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]$를 증가시킨다.

위 알고리즘을 구현한 C 코드는 아래와 같다.

int N,A[MAXN]; char S[MAXN]; void Manachers() { int r = 0, p = 0; for (int i=1;i<=N;i++){ if (i <= r) A[i] = min(A[2*p-i],r-i); else A[i] = 0; while (i-A[i]-1 > 0 && i+A[i]+1 <= N && S[i-A[i]-1] == S[i+A[i]+1]) A[i]++; if (r < i+A[i]) 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] \geq r$이라는 것이다. 이 때, $r$ 값은 while문 도는 회수 만큼 증가하게 된다. 그런데 $r$ 값은 정의에 따라 절대 감소하지 않으므로, wihle 문은 총 $N$번 돈다는 것을 알 수 있다. 따라서 전체 시간복잡도는 $O(N)$이다.

모든 회문 구하기

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

출처: Algospot.com Wiki