Z algorithm
(string/z-algorithm.hpp)

• View this file on GitHub
• Last update: 2024-09-14 20:40:02+09:00
• Include: #include "string/z-algorithm.hpp"

Required by

• string/run-enumerate.hpp

Verified with

• verify/verify-yosupo-string/yosupo-run-enumerate.test.cpp
• verify/verify-yosupo-string/yosupo-z-algorithm.test.cpp

Code

#pragma once

template <typename Container>
vector<int> z_algorithm(const Container& s) {
  int n = s.size();
  if(n == 0) return {};
  vector<int> a(n);
  a[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i + j < n && s[j] == s[i + j]) j++;
    a[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    int k = 1;
    while (i + k < n && k + a[k] < j) a[i + k] = a[k], k++;
    i += k, j -= k;
  }
  return a;
}

/**
 * @brief Z algorithm
 */

#line 2 "string/z-algorithm.hpp"

template <typename Container>
vector<int> z_algorithm(const Container& s) {
  int n = s.size();
  if(n == 0) return {};
  vector<int> a(n);
  a[0] = n;
  int i = 1, j = 0;
  while (i < n) {
    while (i + j < n && s[j] == s[i + j]) j++;
    a[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    int k = 1;
    while (i + k < n && k + a[k] < j) a[i + k] = a[k], k++;
    i += k, j -= k;
  }
  return a;
}

/**
 * @brief Z algorithm
 */

Back to top page