test/zalgo.test.cpp

• View this file on GitHub
• Last update: 2024-03-03 06:51:22+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• Z-Algorithm (C++/string/z-algo.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <iostream>
#include "C++/string/z-algo.hpp"
int main() {
    std::string s;
    std::cin >> s;
    const auto res = zalg(s);
    for(size_t i = 0; i < s.size(); ++i) {
        std::cout << res[i] << " \n"[i + 1 == s.size()];
    }
}

#line 1 "test/zalgo.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <iostream>
#line 2 "C++/string/z-algo.hpp"

#include <vector>
std::vector<int> zalg(const std::string &s) {
    const int n = s.size();
    int j = 0;
    std::vector<int> pre(n);
    for(int i = 1; i < n; ++i) {
        if(i + pre[i - j] < j + pre[j]) pre[i] = pre[i - j];
        else {
            int k = std::max(0, j + pre[j] - i);
            while(i + k < n && s[k] == s[i + k]) ++k;
            pre[i] = k;
            j = i;
        }
    }
    pre.front() = n;
    return pre;
}

/**
 * @brief Z-Algorithm
 */
#line 4 "test/zalgo.test.cpp"
int main() {
    std::string s;
    std::cin >> s;
    const auto res = zalg(s);
    for(size_t i = 0; i < s.size(); ++i) {
        std::cout << res[i] << " \n"[i + 1 == s.size()];
    }
}

Back to top page