This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <bits/extc++.h> using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; #include "../zf.hpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); string s; cin >> s; auto z = zf(s); z[0] = s.length(); for (auto v : z) cout << v << ' '; }
#line 1 "strings/test/Z_Algorithm.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <bits/extc++.h> using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; #line 2 "strings/zf.hpp" vector<int> zf(const string &s) { int n = (int)s.length(); vector<int> z(n); for (int i = 1, l = 0, r = 0; i < n; ++i) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; } #line 10 "strings/test/Z_Algorithm.test.cpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); string s; cin >> s; auto z = zf(s); z[0] = s.length(); for (auto v : z) cout << v << ' '; }