Z algorithm
(string/z-algorithm.hpp)

• View this file on GitHub
• Last update: 2020-12-09 15:22:26+09:00
• Include: #include "string/z-algorithm.hpp"

Verified with

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

Code

#pragma once

template<typename Container>
vector<int> z_algorithm(Container s) {
  int n = s.size();
  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(Container s) {
  int n = s.size();
  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