This documentation is automatically generated by online-judge-tools/verification-helper
#include "string/zalgorithm.hpp"
#pragma once
template <typename STRING> // string, vector どちらでも
vector<int> zalgorithm(const STRING& s) {
int n = int(s.size());
if (n == 0) return {};
vector<int> z(n);
z[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
int& k = z[i];
k = (j + z[j] <= i) ? 0 : min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}
#line 2 "string/zalgorithm.hpp"
template <typename STRING> // string, vector どちらでも
vector<int> zalgorithm(const STRING& s) {
int n = int(s.size());
if (n == 0) return {};
vector<int> z(n);
z[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
int& k = z[i];
k = (j + z[j] <= i) ? 0 : min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}