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

이 알고리즘은 문자열 \(S\)를 입력으로 받아 다음을 반환한다:
* 문자열 \(S\)와 길이가 같은 정수 배열 \(A\), 각 \(A\)의 원소 \(A[i]\)는 \(i\)번째 문자열을 중심으로 하는 가장 긴 팔린드롬의 반지름의 길이.(즉, \(S[(i-A[i])\cdots (i+A[i])]\)는 팔린드롬이며, \(S[(i-A[i]-1) \cdots (i+A[i]+1)]\)은 팔린드롬이 아니다)

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

알고리즘은 다음과 같다:

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

시간복잡도 분석

\(A[i]\)의 초기값은 세 가지 경우가 있을 수 있다.

• \(A[i]=A[2*p - i] (<R-i)\) 인 경우

\(A[i]\)는 더 이상 증가하지않는다. 대칭점\(m=2*p-i\)에서 \(A[m]\)가 더 이상 증가하지 않았다는 것은, \(S[m-A[m]-1]!=S[m+A[m]+1]\)이었음을 의미한다. 근데 \(i+A[m]<R\) 이므로 \(m-A[m]-1\)과 \(m+A[m]+1\)도 \(p\)를 중심으로 하는 팔린드롬안에 들어갈 것이다. 그러므로 \(S[i-A[m]-1]=S[m+A[m]+1], S[i+A[m]+1]=S[m-A[m]-1]\)이고, \(S[i-A[m]-1]!=S[i+A[m]+1]\)이 되므로 의사코드내에서의 while문은 수행되지 않는다. (그림 참조)

• \(A[i]=R-i (<2[2*p - i])\)
• \(A[i]=0\)

이 두 경우는 \(i+A[i] >= R\)임을 의미한다. 따라서 while문을 다 돌고 나면 \(R = i+A[i]\)가 항상 수행될 것이다. 또한 while문을 한 번 돌때마다 최소한 \(A[i]\)가 \(1\)씩 증가하므로, \(R\)값 역시 while문 수행횟수 이상의 값으로 증가할 것이다. \(R\)값의 정의를 생각해보면, \(R<n\)이고, 절대로 감소하지않는다. 그러므로 while문의 총 실행횟수는 \(amortized O(n)\)이고, 이는 총 시간복잡도이다.

모든 팔린드롬 구하기

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

연습문제

• [[problem:COUNTPALIN]]
• Codeforces 문제: palisection