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의 결과는:

(수정 중)