티스토리 뷰

공부

Manacher's Algorithm

전명우 2014. 8. 13. 16:10

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

$A$

 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 코드는 아래와 같다.


시간복잡도 분석

나올 수 있는 $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

'공부' 카테고리의 다른 글

Grundy Number  (0) 2014.11.13
Suffix Array와 LCP  (13) 2014.08.14
Manacher's Algorithm  (0) 2014.08.13
중국인의 나머지 정리와 확장 유클리드 알고리즘  (0) 2014.07.25
고속 푸리에 변환 (Fast Fourier Theorem, FFT)  (5) 2014.07.25
포함-배제의 원리  (0) 2014.07.20
댓글
댓글쓰기 폼