src/String/ZAlgorithm.hpp

• View this file on GitHub
• Last update: 2020-04-07 02:27:18+09:00
• Include: #include "src/String/ZAlgorithm.hpp"

概要

文字列s[0:]とs[i:]の共通prefixの長さの配列を返す、O(|s|)。

基本的なアイディアは、以前に先頭からの文字列との共通prefixとして計算された値を使い回すこと。 左から順に求める配列aを計算しながら、それまでに一番右まで到達した部分についてaをもう一度たどると先頭とのprefix一致がショートカットできる。

アルゴリズム参考: https://snuke.hatenablog.com/entry/2014/12/03/214243
実装のrm_idx(rightmost index)は、それまでに共通prefixとして一番右まで到達したときのインデックスを表す。 苦労して結構うまく実装できたと思ったらsnukeさんのコードとほとんど同じだった、完…

Verified with

• test/yosupo/zalgorithm.test.cpp

Code

/// @docs src/String/ZAlgorithm.md
template <class T> std::vector<int> Z_algorithm(const T& s) {
    std::vector<int> a(s.size());
    for (int i = 1, rm_idx = 0; i < s.size(); i++) {
        if (a[i - rm_idx] < a[rm_idx] - (i - rm_idx)) {
            a[i] = a[i - rm_idx];
        } else {
            a[i] = std::max(0, a[rm_idx] - (i - rm_idx));
            while (i + a[i] < s.size() && s[a[i]] == s[i + a[i]]) a[i]++;
            rm_idx = i;
        }
    }
    a[0] = s.size();
    return a;
}

#line 1 "src/String/ZAlgorithm.hpp"
/// @docs src/String/ZAlgorithm.md
template <class T> std::vector<int> Z_algorithm(const T& s) {
    std::vector<int> a(s.size());
    for (int i = 1, rm_idx = 0; i < s.size(); i++) {
        if (a[i - rm_idx] < a[rm_idx] - (i - rm_idx)) {
            a[i] = a[i - rm_idx];
        } else {
            a[i] = std::max(0, a[rm_idx] - (i - rm_idx));
            while (i + a[i] < s.size() && s[a[i]] == s[i + a[i]]) a[i]++;
            rm_idx = i;
        }
    }
    a[0] = s.size();
    return a;
}

Back to top page