:warning: Z-algorithm
(string/z-algorithm.hpp)

文字列が与えられたとき，それ自身とその suffix それぞれとの最長共通接頭辞（LCP）の長さを列挙する． 計算量は入力文字列の長さに対する線形時間．

厳密に

以下 0-indexed とする．

二つの文字列の LCP の長さを $\operatorname{lcp}$ で表す． また $s[l:r]$ で $s$ の $l$ 文字目から $r-1$ 文字目までの部分文字列を表すことにする． 文字列 $s$ が与えられたとき $p_i=\operatorname{lcp}(s,s[i:|s|])$ を $0\leq i\lt |s|$ について $O(|s|)$ 時間で列挙する．

アルゴリズム

基本的に前から求めていくが，再利用できる情報は再利用する．

何も工夫せず $p_i$ を求めるには以下のようにすればよい：(⭐︎)．

j = i;
while (s[j - i] == s[j]) j++;
p[i] = j - i;

$p_{i+1}$ の値を考える．

もし $p_1\geq p_i-1$ ならば

\[s[0:p_i-1]=s[1:p_i]=s[i+1:i+p_i]\]

が成り立つため $p_{i+1}\geq p_i-1$ である．特に (⭐︎) における j = i; の部分を $p_i$ について計算した後の値から始めてよい．

逆に $p_1\lt p_i-1$ ならば $p_{i+1}=p_1$ と値が定まる． その後，$p_{i+2}$ について同様の議論を行うことができる．

従って次のようなコードで求められる．

vector<int> ZAlgorithm(string s) {
  int n = s.size();
  vector<int> p(n);
  p[0] = n;
  for (int i = 1, j = i; i < n;) {
    if (j < i) j = i;
    while (j < n && s[j - i] == s[j]) j++;
    p[i] = j - i;
    if (p[i] == 0) {
      i++;
      continue;
    }
    int k = 1;
    while (i + k < n && k + p[k] < p[i]) {
      p[i + k] = p[k];
      k++;
    }
    i += k;
  }
  return p;
}
一つ目の while では j が，二つめの while では（間接的に）i が一回ループするごとに 1 ずつ増加し，どちらも n に達すると停止する．従って計算量は $O( s )$ と評価できる．

Code

#pragma once

template <class T>
vector<int> ZAlgorithm(const T& a) {
  int n = a.size();
  vector<int> p(n);
  p[0] = n;
  for (int i = 1, j = 0; i < n;) {
    while (i + j < n && a[j] == a[i + j]) j++;
    p[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    int k = 1;
    while (i + k < n && k + p[k] < j) {
      p[i + k] = p[k];
      k++;
    }
    i += k;
    j -= k;
  }
  return p;
}
/**
 * @brief Z-algorithm
 * @docs docs/string/z-algorithm.md
 */
#line 2 "string/z-algorithm.hpp"

template <class T>
vector<int> ZAlgorithm(const T& a) {
  int n = a.size();
  vector<int> p(n);
  p[0] = n;
  for (int i = 1, j = 0; i < n;) {
    while (i + j < n && a[j] == a[i + j]) j++;
    p[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    int k = 1;
    while (i + k < n && k + p[k] < j) {
      p[i + k] = p[k];
      k++;
    }
    i += k;
    j -= k;
  }
  return p;
}
/**
 * @brief Z-algorithm
 * @docs docs/string/z-algorithm.md
 */
Back to top page