string/z-algorithm.hpp

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "string/z-algorithm.hpp"

Verified with

• test/yosupo/String/Z-Algorithm.test.cpp

Code

vector<int> z_algo(const string &s){
  const int n = s.size();
  vector<int> z(n);
  z[0] = n;
  int i = 1, j = 0;
  while(i < n){
    while(i + j < n && s[j] == s[i + j]) j++;
    z[i] = j;
    if(!j){
      i++;
      continue;
    }
    int k = 1;
    while(k < j && z[k] + k < j) z[i + k++] = z[k];
    i += k;
    j -= k;
  }
  return z;
}

#line 1 "string/z-algorithm.hpp"
vector<int> z_algo(const string &s){
  const int n = s.size();
  vector<int> z(n);
  z[0] = n;
  int i = 1, j = 0;
  while(i < n){
    while(i + j < n && s[j] == s[i + j]) j++;
    z[i] = j;
    if(!j){
      i++;
      continue;
    }
    int k = 1;
    while(k < j && z[k] + k < j) z[i + k++] = z[k];
    i += k;
    j -= k;
  }
  return z;
}

Back to top page