lib/str/z.hpp

• View this file on GitHub
• Last update: 2024-06-14 20:43:15+08:00
• Include: #include "lib/str/z.hpp"

Verified with

• verify/str/zalgorithm.test.cpp

Code

#include <vector>
#include <string>

std::vector<int> z_algorithm(const std::string &s)
{
  int n = s.size();
  std::vector<int> z(n + 1);
  z[0] = n;
  int l = 0, r = 0;
  for (int i = 1; i <= n; i++) {
    int t = 0;
    if (i <= r) t = std::min(z[i - l], r - i);
    while (i + t < n && s[t] == s[i + t]) t++;
    z[i] = t;
    if (i + z[i] > r) {
      l = i;
      r = i + z[i];
    }
  }
  return z;
}

#line 1 "lib/str/z.hpp"
#include <vector>
#include <string>

std::vector<int> z_algorithm(const std::string &s)
{
  int n = s.size();
  std::vector<int> z(n + 1);
  z[0] = n;
  int l = 0, r = 0;
  for (int i = 1; i <= n; i++) {
    int t = 0;
    if (i <= r) t = std::min(z[i - l], r - i);
    while (i + t < n && s[t] == s[i + t]) t++;
    z[i] = t;
    if (i + z[i] > r) {
      l = i;
      r = i + z[i];
    }
  }
  return z;
}

Back to top page