test/yosupo/string/zalgorithm.test.cpp

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/zalgorithm
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include "string/hashint.hpp"
#include "string/rolling_hash.hpp"
#include "string/z_algorithm.hpp"

int main(void) {
    std::string s;
    std::cin >> s;
    int n = s.size();

    auto z = z_algorithm(s);

    RollingHash rh(s);
    std::vector<int> z_hash = {n};
    std::unordered_set<HashInt> st;
    for (int i = 1; i <= n; ++i) st.emplace(rh.get(0, i));
    for (int i = 1; i < n; ++i) {
        int l = 0, r = n - i + 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (st.count(rh.get(i, i + m))) l = m;
            else r = m;
        }
        z_hash.emplace_back(l);
    }

    assert(z == z_hash);
    for (int i = 0; i < n; ++i) std::cout << z[i] << (i == n - 1 ? '\n' : ' ');

    return 0;
}