Verify/z_algorithm.test.cpp

View this file on GitHub
Last update: 2020-07-26 22:31:04+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

String/z_algorithm.hpp

Code

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

#include "../String/z_algorithm.hpp"

#include <iostream>
#include <string>

int main() {
    std::cin.tie();
    std::ios::sync_with_stdio(false);

    std::string s;
    std::cin >> s;

    auto ans = zalgo(s);
    for (auto a : ans) std::cout << a << " ";
    std::cout << "\n";

    return 0;
}

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

#line 2 "String/z_algorithm.hpp"

#include <vector>

template <class Container>
std::vector<int> zalgo(const Container& dat) {
    int n = dat.size();

    std::vector<int> ret(n);
    ret[0] = n;

    int i = 1, len = 0;
    while (i < n) {
        while (i + len < n && dat[len] == dat[i + len]) {
            ++len;
        }
        ret[i] = len;

        if (len == 0) {
            ++i;
            continue;
        }

        int nlen = 1;
        while (i + nlen < n && nlen + ret[nlen] < len) {
            ret[i + nlen] = ret[nlen];
            ++nlen;
        }

        i += nlen;
        len -= nlen;
    }

    return ret;
}
#line 4 "Verify/z_algorithm.test.cpp"

#include <iostream>
#include <string>

int main() {
    std::cin.tie();
    std::ios::sync_with_stdio(false);

    std::string s;
    std::cin >> s;

    auto ans = zalgo(s);
    for (auto a : ans) std::cout << a << " ";
    std::cout << "\n";

    return 0;
}