Manacher

コードについての説明

文字列 $S$ が与えられたとき $0 \le i < n$ について $S[i]$ を中心とする最長の(奇数長の)回文の半径を求める線形時間アルゴリズム(参考).
(注) 以下の説明より (参考) の記事を見たほうがわかりやすい.
$1$ つ目の while 文では愚直に $i$ を中心とする回文の半径 $res[i] (= j)$ を求めています. これだけだと線形にならないので $2$ つ目の while 文で $i$ を中心とする最長回文の中に $S[i-k]$ を中心とする最長の回文が含まれている($k + res[i-k] < j$)なら $S[i+k]$ と $S[i-k]$ を中心とする最長の回文はそれぞれ同じなので更新する. 完全に含まれていなくても部分的に含まれていればその情報は利用できるので while 文を抜けた後は $j \leftarrow j - k$ とし次のループで $S[i+k]$ を中心とする最長回文を調べるときにキョリ $j - k + 1$ 番目の部分から始めることにする.
計算量を考える. まず $1$ つ目の while ループは $i + j$ の値に注目することで bound できる. $i + j$ は $1$ つ目のループを回るごとに $1$ 増え, $2$ つ目のループでは変化しない. $i + j$ は(位置)+(半径)より $|S|$ 以下なので $1$ つ目の while ループを回る回数は高々 $|S|$ 回. $2$ つ目の while ループは $i$ の値に注目することで bound できる. $i$ は $1$ つ目のループでは変化せず $2$ つ目の while ループでは回るごとに $1$ 増える. $i$ は $|S|$ 以下なので $2$ つ目の while ループを回る回数は高々 $|S|$ 回. よって合わせて $\O (|S|)$ となる.

時間計算量: $\O (|S|)$

コード

// i を中心とする最長の回文の半径を res[i] に格納
// S = ababa ⇒ res = {1,2,3,2,1}
// abaab を $a$b$a$a$b$ みたいにすることで偶数長の最長回文も求められる.
void manacher(const string& S,vector<int>& res)
{
    int sz = (int)S.size(), i = 0, j = 0, k;
    res.resize(sz);
    while(i < sz){
        while(i-j >= 0 && i+j < sz && S[i-j] == S[i+j]) j++;
        res[i] = j, k = 1;
        while(i-k >= 0 && i+k < sz && k+res[i-k] < j){
            res[i+k] = res[i-k], k++;
        }
        i += k; j -= k;
    }
}