Halc's Library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by halc-git Hosted on GitHub Pages — Theme by mattgraham

String/Z_algorithm.hpp

• View this file on GitHub
• Last update: 2024-05-09 17:59:47+09:00
• Include: #include "String/Z_algorithm.hpp"
• Link: https://snuke.hatenablog.com/entry/2014/12/03/214243

Verified with

• Verify/verify-yosupo-string/zalgorithm.test.cpp

Code

#pragma once
#include <cstdint>
#include <vector>
// https://snuke.hatenablog.com/entry/2014/12/03/214243
template <typename S>
std::vector<int32_t> z_algorithm(S s) {
    int32_t sz = s.size(), i = 1, j = 0, k;
    std::vector<int32_t> ret(sz);
    ret[0] = sz;
    while (i < sz) {
        while (i + j < sz && s[j] == s[i + j]) j++;
        ret[i] = j;
        if (j == 0) {
            i++;
            continue;
        }
        k = 1;
        while (i + k < sz && k + ret[k] < j) {
            ret[i + k] = ret[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

#line 2 "String/Z_algorithm.hpp"
#include <cstdint>
#include <vector>
// https://snuke.hatenablog.com/entry/2014/12/03/214243
template <typename S>
std::vector<int32_t> z_algorithm(S s) {
    int32_t sz = s.size(), i = 1, j = 0, k;
    std::vector<int32_t> ret(sz);
    ret[0] = sz;
    while (i < sz) {
        while (i + j < sz && s[j] == s[i + j]) j++;
        ret[i] = j;
        if (j == 0) {
            i++;
            continue;
        }
        k = 1;
        while (i + k < sz && k + ret[k] < j) {
            ret[i + k] = ret[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

Back to top page