Z Array
(string/z_array.hpp)

• View this file on GitHub
• Last update: 2024-01-07 22:05:53+09:00
• Include: #include "string/z_array.hpp"

Description

Z array は，文字列 S と S[i:] の最長共通接頭辞の長さを表す配列である．Z array を求めるアルゴリズムは Z algorithm と呼ばれる．

Z array を用いると文字列中のパターンをすべて検索することができる．文字列を S，パターンを P とし，P$S ($ は S にも P にも含まれない文字) の Z array を構築すると，値が P の長さと一致するところで P が現れる．

Operations

• vector<int> z_array(string s)
  • Z array を構築する
  • 時間計算量: $O(n)$

Reference

• Z algorithm (Linear time pattern searching Algorithm)

Required by

• Enumerate Runs (string/enumerate_runs.hpp)

Verified with

• test/yosupo/runenumerate.test.cpp
• test/yosupo/zalgorithm.test.cpp

Code

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

std::vector<int> z_array(const std::string& s) {
    const int n = s.size();
    std::vector<int> z(n);
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        int k = i - l;
        if (i <= r && z[k] < r - i + 1) {
            z[i] = z[k];
        } else {
            l = i;
            if (i > r) r = i;
            while (r < n && s[r - l] == s[r]) ++r;
            --r;
            z[i] = r - l + 1;
        }
    }
    return z;
}

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

std::vector<int> z_array(const std::string& s) {
    const int n = s.size();
    std::vector<int> z(n);
    z[0] = n;
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        int k = i - l;
        if (i <= r && z[k] < r - i + 1) {
            z[i] = z[k];
        } else {
            l = i;
            if (i > r) r = i;
            while (r < n && s[r - l] == s[r]) ++r;
            --r;
            z[i] = r - l + 1;
        }
    }
    return z;
}

Back to top page