(알고리즘)Manacher's Algorithm (팰린드롬)

Manacher's algorithm은 문자열 내에서 팔린드롬(palindrome,회문)을 찾는것과 관련된 알고리즘이며, 시간 복잡도는 O(n) 이다.(n은 문자열의 길이)
이 알고리즘은 문자열 S를 입력으로 받아 다음을 반환한다:
  • 문자열 S와 길이가 같은 정수 배열 A, 각 A의 원소 A[i]는 i번째 문자열을 중심으로 하는 가장 긴 팔린드롬의 반지름의 길이.(즉, S[(iA[i])(i+A[i])]는 팔린드롬이며, S[(iA[i]1)(i+A[i]+1)]은 팔린드롬이 아니다)
예를 들면, S='banana'라는 입력에 대해 A의 결과는:
S[i]banana
A[i]001210
알고리즘은 다음과 같다:
  1. i는 0부터 n1(n=|S|)까지 진행된다
  2. j<i인 모든 j에 대해 R=max(j+A[j])이라하고, 또한 그러한 j를 p라 하자. 즉, R=p+A[p]
  3. iR인지 여부에 따라 A[i]의 초기값이 정해진다
    • i>R이라면, A[i]의 초기값은 0이다.
    • iR이라면, i는 p를 중심으로 한 팔린드롬에 속한다는 이야기이다. 이때 p를 중심으로 i의 대칭점 i을 구한다. (즉, i=2piA[i]의 초기값은 min(Ri,A[i])으로 둔다.
  4. A[i]의 초기값에서부터, S[iA[i]]과 S[i+A[i]]가 같을 때까지 A[i]를 증가시키고, 그 다음 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]의 초기값은 세 가지 경우가 있을 수 있다.
  • A[i]=A[2pi](<Ri) 인 경우
A[i]는 더 이상 증가하지않는다. 대칭점m=2pi에서 A[m]가 더 이상 증가하지 않았다는 것은, S[mA[m]1]!=S[m+A[m]+1]이었음을 의미한다. 근데 i+A[m]<R 이므로 mA[m]1과 m+A[m]+1도 p를 중심으로 하는 팔린드롬안에 들어갈 것이다. 그러므로 S[iA[m]1]=S[m+A[m]+1],S[i+A[m]+1]=S[mA[m]1]이고, S[iA[m]1]!=S[i+A[m]+1]이 되므로 의사코드내에서의 while문은 수행되지 않는다. (그림 참조)
  • A[i]=Ri(<2[2pi])
  • A[i]=0
이 두 경우는 i+A[i]>=R임을 의미한다. 따라서 while문을 다 돌고 나면 R=i+A[i]가 항상 수행될 것이다. 또한 while문을 한 번 돌때마다 최소한 A[i]가 1씩 증가하므로, R값 역시 while문 수행횟수 이상의 값으로 증가할 것이다. R값의 정의를 생각해보면, R<n이고, 절대로 감소하지않는다. 그러므로 while문의 총 실행횟수는 amortizedO(n)이고, 이는 총 시간복잡도이다.

모든 팔린드롬 구하기

Manacher's algorithm은 각 문자를 중심으로 하는 팔린드롬을 측정하기 때문에, 길이가 짝수인 팔린드롬은 찾을 수 없다. (예:abcddcba) 각 글자 사이에 더미 문자를 끼워넣어서 'a#b#c#d#d#c#b#a'꼴로 만들고 풀면, 짝수길이인 팔린드롬 역시 찾을 수 있다.


참고: https://algospot.com/wiki/read/Manacher's_algorithm
참고: http://articles.leetcode.com/longest-palindromic-substring-part-ii/

댓글

이 블로그의 인기 게시물

(ElasticSearch) 결과에서 순서 정렬

(네트워크)폴링방식 vs 롱 폴링방식

(18장) WebSocekt과 STOMP를 사용하여 메시징하기