This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub EarthMessenger/icpc-snippet
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <iostream> #include <string> #include "lib/str/z.hpp" int main() { std::string s; std::cin >> s; auto res = z_algorithm(s); res.pop_back(); for (auto i : res) std::cout << i << " "; std::cout << std::endl; }
#line 1 "verify/str/zalgorithm.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <iostream> #include <string> #line 1 "lib/str/z.hpp" #include <vector> #line 3 "lib/str/z.hpp" 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 6 "verify/str/zalgorithm.test.cpp" int main() { std::string s; std::cin >> s; auto res = z_algorithm(s); res.pop_back(); for (auto i : res) std::cout << i << " "; std::cout << std::endl; }