最長回文半径のテーブル
概要
文字列 $s$ の $s_i$ を中心とする連続する部分文字列が，最大で左右何文字まで回文かという値を $\mathrm{rad}[i]$ とする．Manacher のアルゴリズムは全ての $i$ に対し $\mathrm{rad}[i]$ を高速に計算する．この定義では奇数長にしか対応できないが，各文字の両側にドルマークを挟むことで偶数長にも対応可 (検証コードを参照)．
計算量
$O(n)$
使い方
manacher(s)- s の rad 配列を返す
insert_doller(s)- 偶数長に対応するためにドル記号を挟む
is_palindrome(l, r, rad)- [l, r) が回文か判定する．l, r はそのまま，rad はドル記号を挿入後に構築したものとする (以下同様)．
count_even_palindrome(k, rad)- s[k] と s[k+1] を中心とする偶数長回文の個数
count_odd_palindrome(k, rad)- s[k] を中心とする奇数長回文の個数
実装
std::vector<int> manacher(const std::string &s) {
int n = s.size();
std::vector<int> rad(n);
int c = 0;
for (int r = 0; r < n; ++r) {
int l = c - (r - c);
if (r + rad[l] < c + rad[c]) {
rad[r] = rad[l];
} else {
int rr = c + rad[c];
int rl = r - (rr - r);
while (rl >= 0 && rr < n && s[rl] == s[rr]) ++rr, --rl;
rad[r] = rr - r;
c = r;
}
}
return rad;
}
std::string insert_dollar(const std::string &s) {
int n = s.size();
std::string res(n * 2 + 1, '$');
for (int i = 0; i < n; ++i) {
res[i * 2 + 1] = s[i];
}
return res;
}
bool is_palindrome(int l, int r, const std::vector<int> &rad) {
l = l * 2 + 1;
r = (r - 1) * 2 + 1;
int c = (l + r) / 2;
return r < c + rad[c];
}
int count_even_parindrome(int k, const std::vector<int> &rad) { return (rad[2 * k + 2] - 1) / 2; }
int count_odd_parindrome(int k, const std::vector<int> &rad) { return (rad[2 * k + 1] + 1) / 2; }
検証
yukicoder No. 464 PPAP http://yukicoder.me/submissions/149615