strings/Z.h

• View this file on GitHub
• Last update: 2025-11-18 22:42:15+07:00

Verified with

• tests/Z_Algorithm.test.cpp

Code

vi Z(const string& S) {
  vi z(sz(S));
  int l = -1, r = -1;
  for (int i = 1; i < sz(S); ++i) {
    z[i] = i >= r ? 0 : min(r - i, z[i - l]);
    while (i + z[i] < sz(S) && S[i + z[i]] == S[z[i]]) z[i]++;
    if (i + z[i] > r) l = i, r = i + z[i];
  }
  return z;
}

#line 1 "strings/Z.h"
vi Z(const string& S) {
  vi z(sz(S));
  int l = -1, r = -1;
  for (int i = 1; i < sz(S); ++i) {
    z[i] = i >= r ? 0 : min(r - i, z[i - l]);
    while (i + z[i] < sz(S) && S[i + z[i]] == S[z[i]]) z[i]++;
    if (i + z[i] > r) l = i, r = i + z[i];
  }
  return z;
}

Back to top page