sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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"); }