string/z_algorithm.hpp

• View this file on GitHub
• Last update: 2022-07-30 11:55:56+09:00
• Include: #include "string/z_algorithm.hpp"

Verified with

• string/test/zalgorithm.test.cpp

Code

#pragma once

#include <vector>

template <typename Cont>
std::vector<int> z_algorithm(const Cont &s) {
    if (s.empty()) {
        return std::vector<int>(0);
    }
    std::vector<int> z(s.size());
    z[0] = (int) s.size();
    int i = 1, j = 0;
    while (i < (int) s.size()) {
        while (i + j < (int) s.size() && s[i + j] == s[j]) {
            ++j;
        }
        z[i] = j;
        if (j == 0) {
            ++i;
            continue;
        }
        int k = 1;
        while (k < j && k + z[k] < j) {
            z[i + k] = z[k];
            ++k;
        }
        i += k;
        j -= k;
    }
    return z;
}

#line 2 "string/z_algorithm.hpp"

#include <vector>

template <typename Cont>
std::vector<int> z_algorithm(const Cont &s) {
    if (s.empty()) {
        return std::vector<int>(0);
    }
    std::vector<int> z(s.size());
    z[0] = (int) s.size();
    int i = 1, j = 0;
    while (i < (int) s.size()) {
        while (i + j < (int) s.size() && s[i + j] == s[j]) {
            ++j;
        }
        z[i] = j;
        if (j == 0) {
            ++i;
            continue;
        }
        int k = 1;
        while (k < j && k + z[k] < j) {
            z[i + k] = z[k];
            ++k;
        }
        i += k;
        j -= k;
    }
    return z;
}

Back to top page