ホーム > libalgo

最長回文半径のテーブル

概要

文字列 $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

参考文献

http://snuke.hatenablog.com/entry/2014/12/02/235837