Manacher による最大長回文探索アルゴリズム

Manacher は人名.

文字列 \(s\) が与えられた時、\(s\) の各点を中心とする回文の最大長を求める. ここで \(n = |s|\) とすると、各点とは

の二種類のこと. \(i\) は各文字に対応し、\(j\) は隣り合った2文字の間を指す. これを中心とする (連続) 部分文字列とは

のこと.

以下ソースコードは Spaghetthi Source 1 より拝借したものを多少自分好みにアレンジしたもの. いずれも返り値は \[1, (1, 2), 2, (2, 3), 3, \ldots, n-1, (n-1, n)\] を中心としたする回分の最大長を収めたベクトル.

string.manacher.rs

fn manacher<A: Ord>(s: &Vec<A>) -> Vec<usize> {
    let n = s.len();
    let mut r = vec![0; 2 * n - 1];
    let mut i = 0;
    let mut j = 0;
    while i < 2 * n - 1 {
        while i >= j && i + j + 1 < 2 * n && s[(i - j) / 2] == s[(i + j + 1) / 2] {
            j += 1;
        }
        r[i] = j;
        let mut k = 1;
        while i + k < 2 * n - 1 && i >= k && r[i] >= k && r[i - k] != r[i] - k {
            r[i + k] = min(r[i - k], r[i] - k);
            k += 1;
        }
        i += k;
        j = if j > k { j - k } else { 0 }
    }
    r
}

string.manacher.cc

vector<int> manacher(string&s) {
    const int n = s.size();
    vector<int> r(2 * n - 1);
    for (int i = 0, j = 0; i < 2 * n - 1;) {
        while (i >= j and i + j + 1 < 2 * n and s[(i - j) / 2] == s[(i + j + 1) / 2]) {
            ++j;
        }
        r[i] = j;
        int k;
        for (k = 1; i >= k and i + k < 2 * n - 1 and r[i] >= k and r[i - k] != r[i] - k; ++k) {
            r[i + k] = min(r[i - k], r[i] - k);
        }
        i += k;
        j = max(j - k, 0);
    }
    return r;
}

参考


  1. Spaghetti Source - 最長回文 (Manacher)