문자열 $s$가 있고, 이 문자열에서 모든 부분 회문을 찾으려 한다고 합시다.
우리는 곧바로 명백한 어려움에 부딪힙니다. 문자열 안에 그런 것이 $O(n^2)$개 있을 수 있는데, 이는 문자열 $s = aa \ldots a$의 예에서 확인할 수 있습니다. 따라서 다음 형식을 사용하겠습니다. 각 위치 $s_i$에 대해 중심이 $s_i$와 일치하는 가장 긴 팰린드롬을 찾습니다(짝수 길이와 홀수 길이 팰린드롬은 따로 다루겠습니다). 그 길이의 절반을 내림한 값을 반지름이라고 부르겠습니다.
단순한 해법은 $s_i$를 차례로 순회하면서, 각 $s_i$에 대해 두 번째 반복문으로 구하려는 최대 길이를 찾는 것입니다:
vector<int> pal_array(string s) {
int n = s.size();
// окружим строку спецсимволами, чтобы не рассматривать выход за границы
s = "#" + s + "$";
// в этом массиве будем хранить расстояние от центра до границы палиндрома
vector<int> t(n, 0);
for(int i = 1; i <= n; i++)
while (s[i - t[i - 1]] == s[i + t[i - 1]])
r[i-1]++;
return r;
}
같은 예시 $s = aa\dots a$를 보면 이 구현이 $O(n^2)$에 동작한다는 것을 알 수 있습니다.
최적화를 위해 Z 함수 알고리즘에서 익숙한 아이디어를 적용합니다: $t_i$를 초기화할 때 이미 계산된 $t$를 활용합니다. 구체적으로는, 지금까지 찾은 부분 회문 중 가장 오른쪽에 있는 것에 해당하는 구간 $(l, r)$을 유지합니다. 그러면 $s_i$를 중심으로 하는 가장 긴 회문 중 $s_{l:r}$ 내부에 놓인 부분의 반지름은 적어도 $\min(r-i, ; t_{l+r-i})$라고 말할 수 있습니다. 첫 번째 값은 그보다 더 나아가면 $s_{l:r}$의 범위를 벗어나게 되는 길이와 같고, 두 번째 값은 회문 $s_{l:r}$의 중심에 대해 대칭인 위치에서의 반지름 값과 같습니다.
vector<int> manacher_odd(string s) {
int n = (int) s.size();
vector<int> d(n, 1);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i < r)
d[i] = min(r - i + 1, d[l + r - i]);
while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]])
d[i]++;
if (i + d[i] - 1 > r)
l = i - d[i] + 1, r = i + d[i] - 1;
}
return d;
}
Z 함수와 마찬가지로 이 알고리즘은 선형 시간에 동작합니다. while 루프는 $t_i = r - i$일 때만 실행되며(그렇지 않으면 팰린드롬이 이미 어딘가에 막힌 것입니다), 루프의 각 반복은 $r$를 1씩 증가시킵니다. $r \leq n$이므로, 이 루프들은 모두 합쳐 $O(n)$번 반복한다는 것을 알 수 있습니다.
짝수 길이 팰린드롬의 경우에는 인덱스만 바뀝니다:
vector<int> manacher_even(string s) {
int n = (int) s.size();
vector<int> d(n, 0);
int l = -1, r = -1;
for (int i = 0; i < n - 1; i++) {
if (i < r)
d[i] = min(r - i, d[l + r - i - 1]);
while (i - d[i] >= 0 && i + d[i] + 1 < n && s[i - d[i]] == s[i + d[i] + 1])
d[i]++;
if (i + d[i] > r)
l = i - d[i] + 1, r = i + d[i];
}
return d;
}
또한 두 가지 구현을 따로 작성하지 않고, 다음과 같은 요령을 사용하여 치환을 할 수도 있습니다:
$$ S = s_1 s_2 \dots s_n \to S^* = s_1 \# s_2 \# \dots \# s_n $$ 이제 $s_i$를 중심으로 하는 홀수 길이 팰린드롬은 원래 문자열의 홀수 길이 팰린드롬에 대응하고,#을 중심으로 하는 홀수 길이 팰린드롬은 짝수 길이 팰린드롬에 대응합니다.