test/string/z_algorithm.test.cpp

View this file on GitHub
Last update: 2023-06-06 22:09:16+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include "../../template/template.hpp"
#include "../../string/z_algorithm.hpp"

using namespace lib;

int main() {
    std::string s;
    std::cin >> s;
    int n = s.size();
    auto z = z_algorithm(s);
    rep(i,0,n) {
        std::cout << z[i] << " \n"[i == n-1];
    }
}

#line 1 "test/string/z_algorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 2 "string/z_algorithm.hpp"

#line 4 "string/z_algorithm.hpp"

namespace lib {

template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {
    int n = int(s.size());
    if (n == 0) return {};
    std::vector<int> z(n);
    z[0] = 0;
    for (int i = 1, j = 0; i < n; i++) {
        int& k = z[i];
        k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
        while (i + k < n && s[k] == s[i + k]) k++;
        if (j + z[j] < i + z[i]) j = i;
    }
    z[0] = n;
    return z;
}

std::vector<int> z_algorithm(const std::string& s) {
    int n = int(s.size());
    std::vector<int> s2(n);
    for (int i = 0; i < n; i++) {
        s2[i] = s[i];
    }
    return z_algorithm(s2);
}

}
#line 5 "test/string/z_algorithm.test.cpp"

using namespace lib;

int main() {
    std::string s;
    std::cin >> s;
    int n = s.size();
    auto z = z_algorithm(s);
    rep(i,0,n) {
        std::cout << z[i] << " \n"[i == n-1];
    }
}