string/zFunc.cpp

• View this file on GitHub
• Last update: 2024-07-15 22:07:26+08:00

Verified with

• test/Z_algorithm.test.cpp

Code

template<class T>
vector<int> zFunc(T &s) {
  vector<int> z(ssize(s));
  z[0] = ssize(s);
  for(int i = 1, l = 0, r = -1; i < ssize(s); i++) {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while(i + z[i] < ssize(s) and s[i + z[i]] == s[z[i]])
      l = i, r = i + z[i], z[i] += 1;
  }
  return z;
}

#line 1 "string/zFunc.cpp"
template<class T>
vector<int> zFunc(T &s) {
  vector<int> z(ssize(s));
  z[0] = ssize(s);
  for(int i = 1, l = 0, r = -1; i < ssize(s); i++) {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while(i + z[i] < ssize(s) and s[i + z[i]] == s[z[i]])
      l = i, r = i + z[i], z[i] += 1;
  }
  return z;
}

Back to top page