test/z_algorithm.yosupo.zalgorithm.test.cpp

View this file on GitHub
Last update: 2020-05-15 17:57:27+09:00
Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

lib/z_algorithm.hpp

Code

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

#include <iostream>
#include <string>
#include "../lib/z_algorithm.hpp"

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

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

#include <iostream>
#include <string>
#line 1 "lib/z_algorithm.hpp"



#include <vector>
#line 6 "lib/z_algorithm.hpp"
#include <algorithm>

std::vector<int> z_algorithm(const std::string &s) {
    int n = s.size();
    std::vector<int> ret(n);
    ret[0] = n;
    int begin = 1, len = 0;
    while (begin < n) {
        while (begin + len < n && s[len] == s[begin + len]) len++;
        ret[begin] = len;
        int t = 1;
        while (t < len && t + ret[t] < len) {
            ret[begin + t] = ret[t];
            t++;
        }
        begin += t; len = std::max(0, len - t);
    }
    return ret;
}


#line 6 "test/z_algorithm.yosupo.zalgorithm.test.cpp"

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