Z Algorithm
(lib/string/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2024-05-04 18:06:16+09:00
• Include: #include "lib/string/z_algorithm.hpp"

Z Algorithm

概要

文字列 $S$ のそれぞれの $i : (0 \leq i < \lvert S\lvert)$ について、$S[1] + S[2] + …$ と $S[i] + S[i + 1] + …$ の最長共通接頭辞の長さ を求めます。

計算量

$\mathrm{O}(\lvert S\lvert)$

Required by

• Run Enumerate (lib/string/run_enumerate.hpp)

Verified with

• test/library_checker/string/runenumerate.test.cpp
• test/library_checker/string/z_algorithm.test.cpp

Code

#pragma once

/**
 * @brief Z Algorithm
 * @docs docs/string/z_algorithm.md
 */

template <typename T>
vector<int> z_algorithm(const T &s) {
    int n = s.size();
    vector<int> res(n, 0);
    for(int i = 1, j = 0; i < n; ++i){
        if(i + res[i - j] < j + res[j]){
            res[i] = res[i - j];
        } else{
            res[i] = max(j + res[j] - i, 0);
            while(i + res[i] < n && s[i + res[i]] == s[res[i]]) ++res[i];
            j = i;
        }
    }
    res[0] = n;
    return res;
}

#line 2 "lib/string/z_algorithm.hpp"

/**
 * @brief Z Algorithm
 * @docs docs/string/z_algorithm.md
 */

template <typename T>
vector<int> z_algorithm(const T &s) {
    int n = s.size();
    vector<int> res(n, 0);
    for(int i = 1, j = 0; i < n; ++i){
        if(i + res[i - j] < j + res[j]){
            res[i] = res[i - j];
        } else{
            res[i] = max(j + res[j] - i, 0);
            while(i + res[i] < n && s[i + res[i]] == s[res[i]]) ++res[i];
            j = i;
        }
    }
    res[0] = n;
    return res;
}

Back to top page