마나커 알고리즘

회문과 중심

회문은 앞에서 읽은 내용과 뒤에서 읽은 내용이 같은 문자열이다. 홀수 길이 회문의 중심은 문자 하나이고, 짝수 길이 회문의 중심은 두 문자 사이다. 마나커 알고리즘은 이 중심들을 기준으로 좌우 대칭인 범위를 계산한다. 문자를 건너뛰는 회문 부분수열 문제와는 다르다.

반지름으로 저장하기

예를 들어 cabac의 가운데 b를 중심으로 한 회문은 b, aba, cabac다. 중심 문자를 포함해 한쪽으로 센 최대 반지름을 3으로 저장하면 길이가 1, 3, 5인 회문이 모두 존재함을 알 수 있다. 짝수 회문에서는 반지름과 전체 길이의 환산 규칙을 따로 정의한다.

대칭 위치의 정보 재사용

이미 확인한 회문 구간 안에서 새 중심을 처리할 때는 기존 중심의 반대편 위치에 저장한 반지름을 참고한다. 확인된 구간을 벗어나지 않는 부분은 재사용하고, 바깥쪽으로 더 확장할 수 있는지만 비교한다. 오른쪽 경계가 전진하는 총량이 제한되므로 전체 계산이 O(n)에 끝난다.

선형 시간의 의미

같은 문자만 n개 이어진 문자열에는 위치가 다른 회문 부분 문자열이 n(n+1)/2개 있다. 따라서 모두의 위치를 개별 출력하는 시간까지 선형이라고 할 수는 없다. 알고리즘이 선형 시간에 만드는 것은 중심별 반지름 정보다. 이 배열에서 최장 회문의 길이나 위치별 회문 개수 등을 얻을 수 있다.