티스토리 뷰
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 |
알고리즘은 다음과 같다.
- $i$는 1부터 $N$ ($N = |S|$)까지 진행된다.
- $j < i$인 모든 $j$에 대해 $r = \max(j+A[j])$이라 하고, 또한 그러한 $j$를 $p$라 하자. 즉, $r = p+A[p]$
- $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'])$이다.
- $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"가 되어 길이가 홀수가 된다.
'공부' 카테고리의 다른 글
Grundy Number (0) | 2014.11.13 |
---|---|
Suffix Array와 LCP (14) | 2014.08.14 |
중국인의 나머지 정리와 확장 유클리드 알고리즘 (0) | 2014.07.25 |
고속 푸리에 변환 (Fast Fourier Theorem, FFT) (9) | 2014.07.25 |
포함-배제의 원리 (0) | 2014.07.20 |
- Total
- Today
- Yesterday
- Knuth Optimization
- vote
- IOI2012
- Splay Tree
- Dijkstra
- Algorithm
- Parametric Search
- USACO
- Segment tree
- moore
- BOI 2001
- Tree
- idea
- Dynamic Pramming
- IOI2011
- BOI 2009
- dynamic programming
- HackerRank
- Divide & Conquer
- ioi
- majority
- TRIE
- z-trening
- Boyer-Moore Majority Vote Algorithm
- IOI2014
- IOI2013
- Greedy Method
- Boyer
- BOI
- optimization
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |