History: Manacher's algorithm

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

이 알고리즘은 문자열S를 입력으로 받아 다음을 반환한다:

  • 문자열 S와 길이가 같은 정수 배열 A, 각 A의 원소 A[i]는 i번째 문자열을 중심으로 하는 가장 긴 팔린드롬의 반지름의 길이.(즉, S[i-A[i]:i+A[i]]는 팔린드롬이며, S[i-A[i]-1:i+A[i]+1]은 팔린드롬이 아니다)

예를 들면, S='banana'라는 입력에 대해 A의 결과는:

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

알고리즘은 다음과 같다:

  1. i0부터 n-1(n=|S|)까지 진행된다
  2. j<i인 모든 j에 대해 R=max(j+A[j])이라하고, 또한 그러한 jp라 하자. 즉, R=p+A[p]
  3. i<=R인지 여부에 따라 A[i]초기값이 정해진다
    • i>R이라면, A[i]의 초기값은 0이다.
    • i<=R이라면, ip를 중심으로 한 팔린드롬에 속한다는 이야기이다. 이때 p를 중심으로 i의 대칭점 i'을 구한다. (즉, i'=2*p-i) A[i]의 초기값은 min(R-i,A[i'])과 같다.
  4. A[i]의 초기값에서부터, S[i-A[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

연습문제