sotanishy's code snippets for competitive programming
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <bits/stdc++.h>
#include "../../string/z_array.hpp"
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string S;
cin >> S;
vector<int> z = z_array(S);
for (int i = 0; i < S.size(); ++i)
cout << z[i] << (i < S.size() - 1 ? " " : "\n");
}
#line 1 "test/yosupo/zalgorithm.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"
#include <bits/stdc++.h>
#line 4 "string/z_array.hpp"
std::vector<int> z_array(const std::string& s) {
const int n = s.size();
std::vector<int> z(n);
z[0] = n;
int l = 0, r = 0;
for (int i = 1; i < n; ++i) {
int k = i - l;
if (i <= r && z[k] < r - i + 1) {
z[i] = z[k];
} else {
l = i;
if (i > r) r = i;
while (r < n && s[r - l] == s[r]) ++r;
--r;
z[i] = r - l + 1;
}
}
return z;
}
#line 6 "test/yosupo/zalgorithm.test.cpp"
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string S;
cin >> S;
vector<int> z = z_array(S);
for (int i = 0; i < S.size(); ++i)
cout << z[i] << (i < S.size() - 1 ? " " : "\n");
}