Luzhiled's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub ei1333/library

:heavy_check_mark: test/verify/yosupo-zalgorithm.test.cpp

Depends on

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
// clang-format on

#include <iostream>
#include <string>

#include "../../string/z-algorithm.hpp"

using namespace std;

int main() {
  string s;
  cin >> s;
  auto z = ZAlgorithm(s).get();
  for (int i = 0; i < static_cast<int>(z.size()); i++) {
    if (i > 0) cout << " ";
    cout << z[i];
  }
  cout << "\n";
}
#line 1 "test/verify/yosupo-zalgorithm.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
// clang-format on

#include <iostream>
#include <string>

#line 1 "string/z-algorithm.hpp"
/**
 * @brief Z Algorithm
 * @see https://heno239.hatenablog.com/entry/2020/07/07/140651
 *
 */
#line 7 "string/z-algorithm.hpp"

#include <queue>
#include <vector>

template <typename T = char>
struct ZAlgorithm {
 private:
  std::vector<T> s;
  std::vector<int> deleted;
  std::vector<std::vector<int> > delete_hist;
  std::vector<int> z;
  std::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); }

  std::vector<int> get() {
    std::vector<int> ret(s.size());
    for (int i = 0; i < (int)s.size(); i++) {
      ret[i] = get(i);
    }
    return ret;
  }
};
#line 9 "test/verify/yosupo-zalgorithm.test.cpp"

using namespace std;

int main() {
  string s;
  cin >> s;
  auto z = ZAlgorithm(s).get();
  for (int i = 0; i < static_cast<int>(z.size()); i++) {
    if (i > 0) cout << " ";
    cout << z[i];
  }
  cout << "\n";
}

Test cases

Env Name Status Elapsed Memory
g++ all_same_00 :heavy_check_mark: AC 50 ms 25 MB
g++ all_same_01 :heavy_check_mark: AC 49 ms 25 MB
g++ all_same_02 :heavy_check_mark: AC 48 ms 25 MB
g++ all_same_03 :heavy_check_mark: AC 55 ms 25 MB
g++ all_same_04 :heavy_check_mark: AC 50 ms 25 MB
g++ binary_carry_00 :heavy_check_mark: AC 50 ms 26 MB
g++ binary_carry_01 :heavy_check_mark: AC 46 ms 26 MB
g++ example_00 :heavy_check_mark: AC 2 ms 4 MB
g++ example_01 :heavy_check_mark: AC 2 ms 4 MB
g++ example_02 :heavy_check_mark: AC 2 ms 4 MB
g++ example_03 :heavy_check_mark: AC 2 ms 4 MB
g++ fib_str_00 :heavy_check_mark: AC 48 ms 27 MB
g++ fib_str_01 :heavy_check_mark: AC 36 ms 20 MB
g++ fib_str_02 :heavy_check_mark: AC 37 ms 20 MB
g++ fib_str_03 :heavy_check_mark: AC 38 ms 20 MB
g++ fib_str_04 :heavy_check_mark: AC 46 ms 25 MB
g++ hack606_00 :heavy_check_mark: AC 2 ms 4 MB
g++ max_random_00 :heavy_check_mark: AC 46 ms 24 MB
g++ max_random_01 :heavy_check_mark: AC 44 ms 24 MB
g++ random_00 :heavy_check_mark: AC 38 ms 20 MB
g++ random_01 :heavy_check_mark: AC 42 ms 23 MB
g++ random_02 :heavy_check_mark: AC 7 ms 6 MB
g++ random_03 :heavy_check_mark: AC 38 ms 21 MB
g++ random_04 :heavy_check_mark: AC 29 ms 20 MB
g++ random_05 :heavy_check_mark: AC 31 ms 20 MB
g++ random_06 :heavy_check_mark: AC 44 ms 22 MB
g++ random_07 :heavy_check_mark: AC 11 ms 8 MB
g++ random_08 :heavy_check_mark: AC 29 ms 20 MB
g++ random_09 :heavy_check_mark: AC 11 ms 8 MB
clang++ all_same_00 :heavy_check_mark: AC 50 ms 25 MB
clang++ all_same_01 :heavy_check_mark: AC 52 ms 25 MB
clang++ all_same_02 :heavy_check_mark: AC 51 ms 25 MB
clang++ all_same_03 :heavy_check_mark: AC 54 ms 25 MB
clang++ all_same_04 :heavy_check_mark: AC 49 ms 25 MB
clang++ binary_carry_00 :heavy_check_mark: AC 49 ms 26 MB
clang++ binary_carry_01 :heavy_check_mark: AC 47 ms 26 MB
clang++ example_00 :heavy_check_mark: AC 2 ms 4 MB
clang++ example_01 :heavy_check_mark: AC 2 ms 3 MB
clang++ example_02 :heavy_check_mark: AC 2 ms 4 MB
clang++ example_03 :heavy_check_mark: AC 2 ms 3 MB
clang++ fib_str_00 :heavy_check_mark: AC 48 ms 26 MB
clang++ fib_str_01 :heavy_check_mark: AC 36 ms 20 MB
clang++ fib_str_02 :heavy_check_mark: AC 35 ms 20 MB
clang++ fib_str_03 :heavy_check_mark: AC 33 ms 20 MB
clang++ fib_str_04 :heavy_check_mark: AC 47 ms 25 MB
clang++ hack606_00 :heavy_check_mark: AC 2 ms 4 MB
clang++ max_random_00 :heavy_check_mark: AC 45 ms 24 MB
clang++ max_random_01 :heavy_check_mark: AC 46 ms 24 MB
clang++ random_00 :heavy_check_mark: AC 39 ms 20 MB
clang++ random_01 :heavy_check_mark: AC 44 ms 22 MB
clang++ random_02 :heavy_check_mark: AC 7 ms 6 MB
clang++ random_03 :heavy_check_mark: AC 40 ms 21 MB
clang++ random_04 :heavy_check_mark: AC 29 ms 20 MB
clang++ random_05 :heavy_check_mark: AC 32 ms 20 MB
clang++ random_06 :heavy_check_mark: AC 42 ms 22 MB
clang++ random_07 :heavy_check_mark: AC 10 ms 8 MB
clang++ random_08 :heavy_check_mark: AC 28 ms 20 MB
clang++ random_09 :heavy_check_mark: AC 12 ms 8 MB
Back to top page