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
~~~

연습문제

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