Z Algorithm
(string/z_algorithm.hpp)

• View this file on GitHub
• Last update: 2022-09-02 02:22:16+09:00
• Include: #include "string/z_algorithm.hpp"

Z Algorithm

列のそれぞれの接尾辞について、列全体との最長共通接頭辞の長さを求める。

vector<int> z_algorithm(const T &A)

$A$ を長さ $N$ の列とするとき、長さ $N$ の列 $Z$ を返す。ただし、$0 \leq i < N$ について $Z_i$ は $A$ と $A[i,N)$ の最長共通接頭辞の長さである。

時間計算量は $O(N)$ である。

Verified with

• test/library_checker/string/zalgorithm.test.cpp

Code

#pragma once
template <typename T>
vector<int> z_algorithm(const T &A){
  int N = A.size();
  vector<int> Z(N, 0);
  for (int i = 1, j = 0; i < N; i++){
    if (i + Z[i - j] < j + Z[j]){
      Z[i] = Z[i - j];
    } else {
      int k = max(0, j + Z[j] - i);
      while (i + k < N && A[k] == A[i + k]){
        k++;
      }
      Z[i] = k;
      j = i;
    }
  }
  Z[0] = N;
  return Z;
}

#line 2 "string/z_algorithm.hpp"
template <typename T>
vector<int> z_algorithm(const T &A){
  int N = A.size();
  vector<int> Z(N, 0);
  for (int i = 1, j = 0; i < N; i++){
    if (i + Z[i - j] < j + Z[j]){
      Z[i] = Z[i - j];
    } else {
      int k = max(0, j + Z[j] - i);
      while (i + k < N && A[k] == A[i + k]){
        k++;
      }
      Z[i] = k;
      j = i;
    }
  }
  Z[0] = N;
  return Z;
}

Back to top page