Z Algorithm (string/z-algorithm.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "string/z-algorithm.hpp"
• Link: https://heno239.hatenablog.com/entry/2020/07/07/140651

概要

文字列 $S$ が与えられたとき, それぞれの $i$ について $S$ と $S[i, |S|]$ の最長共通接頭辞の長さを記録した配列を線形時間で構築する.

具体例を以下に示す. 例えば $i = 5$ のときの最長共通接頭辞は “aaa”, つまり $3$ 文字である.

aaabaaaab
921034210

使い方

• ZAlgorithm(): 空文字列で初期化する.
• ZAlgorithm(s): 文字列 s で初期化する.
• add(c): 文字列の末尾に c を追加する.
• get(k): 現時点の文字列の $S$ と $S[i, |S|]$ の最長共通接頭辞の長さを返す
• get(): 現時点の文字列の $S$ とすべての $i$ についての$S[i, |S|]$ の最長共通接頭辞の長さを返す.

計算量

• 全体で $O(|S|)$

Verified with

• test/verify/yosupo-zalgorithm.test.cpp

Code

/**
 * @brief Z Algorithm
 * @see https://heno239.hatenablog.com/entry/2020/07/07/140651
 *
 */
template <typename T = char>
struct ZAlgorithm {
 private:
  vector<T> s;
  vector<int> deleted;
  vector<vector<int> > delete_hist;
  vector<int> z;
  queue<int> cur;

 public:
  ZAlgorithm() : delete_hist{{}} {}

  template <typename S>
  ZAlgorithm(const S &s) : ZAlgorithm() {
    for (auto &c : s) add(c);
  }

  void add(const T &c) {
    s.emplace_back(c);
    delete_hist.emplace_back();
    deleted.emplace_back(0);
    z.emplace_back(0);
    z[0]++;

    int len = (int)s.size();
    if (len == 1) return;
    if (s[0] == c)
      cur.emplace(len - 1);
    else
      deleted[len - 1] = 1;

    auto set = [&](int t, int len) {
      deleted[t] = 1;
      delete_hist[len].emplace_back(t);
      z[t] = len - t - 1;
    };

    while (not cur.empty()) {
      int t = cur.front();
      if (deleted[t]) {
        cur.pop();
      } else if (s[len - t - 1] == s.back()) {
        break;
      } else {
        set(t, len);
        cur.pop();
      }
    }

    if (not cur.empty()) {
      int t = cur.front();
      for (auto &p : delete_hist[len - t]) {
        set(p + t, len);
      }
    }
  }

  int get(int k) const { return deleted[k] ? z[k] : (int)s.size() - k; }

  int operator[](int k) const { return get(k); }

  vector<int> get() {
    vector<int> ret(s.size());
    for (int i = 0; i < (int)s.size(); i++) {
      ret[i] = get(i);
    }
    return ret;
  }
};

#line 1 "string/z-algorithm.hpp"
/**
 * @brief Z Algorithm
 * @see https://heno239.hatenablog.com/entry/2020/07/07/140651
 *
 */
template <typename T = char>
struct ZAlgorithm {
 private:
  vector<T> s;
  vector<int> deleted;
  vector<vector<int> > delete_hist;
  vector<int> z;
  queue<int> cur;

 public:
  ZAlgorithm() : delete_hist{{}} {}

  template <typename S>
  ZAlgorithm(const S &s) : ZAlgorithm() {
    for (auto &c : s) add(c);
  }

  void add(const T &c) {
    s.emplace_back(c);
    delete_hist.emplace_back();
    deleted.emplace_back(0);
    z.emplace_back(0);
    z[0]++;

    int len = (int)s.size();
    if (len == 1) return;
    if (s[0] == c)
      cur.emplace(len - 1);
    else
      deleted[len - 1] = 1;

    auto set = [&](int t, int len) {
      deleted[t] = 1;
      delete_hist[len].emplace_back(t);
      z[t] = len - t - 1;
    };

    while (not cur.empty()) {
      int t = cur.front();
      if (deleted[t]) {
        cur.pop();
      } else if (s[len - t - 1] == s.back()) {
        break;
      } else {
        set(t, len);
        cur.pop();
      }
    }

    if (not cur.empty()) {
      int t = cur.front();
      for (auto &p : delete_hist[len - t]) {
        set(p + t, len);
      }
    }
  }

  int get(int k) const { return deleted[k] ? z[k] : (int)s.size() - k; }

  int operator[](int k) const { return get(k); }

  vector<int> get() {
    vector<int> ret(s.size());
    for (int i = 0; i < (int)s.size(); i++) {
      ret[i] = get(i);
    }
    return ret;
  }
};

Back to top page