Zalgorithm (string/z_algorithm.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-04-21 17:58:31+09:00
• Include: #include "string/z_algorithm.hpp"

文字列の最長共通接頭辞を$\Theta(N)$で求める。

Verified with

• test/zalgorithm.test.cpp

Code

#pragma once
#include <cstdint>
#include <string>
#include <vector>

inline std::vector<int> Zalgorithm(const std::string& s) noexcept {
    std::vector<int> Z(s.size());
    Z[0] = s.size();
    for (uint32_t i = 1, j = 0, siz = s.size(); i < siz;) {
        while (i + j < siz && s[j] == s[i + j]) {
            ++j;
        }
        Z[i] = j;
        if (j == 0) {
            ++i;
        } else {
            uint32_t k = 1;
            for (; k < j && k + Z[k] < j; ++k) {
                Z[i + k] = Z[k];
            }
            i += k;
            j -= k;
        }
    }
    return Z;
}

#line 2 "string/z_algorithm.hpp"
#include <cstdint>
#include <string>
#include <vector>

inline std::vector<int> Zalgorithm(const std::string& s) noexcept {
    std::vector<int> Z(s.size());
    Z[0] = s.size();
    for (uint32_t i = 1, j = 0, siz = s.size(); i < siz;) {
        while (i + j < siz && s[j] == s[i + j]) {
            ++j;
        }
        Z[i] = j;
        if (j == 0) {
            ++i;
        } else {
            uint32_t k = 1;
            for (; k < j && k + Z[k] < j; ++k) {
                Z[i + k] = Z[k];
            }
            i += k;
            j -= k;
        }
    }
    return Z;
}

Back to top page