This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <iostream> #include "C++/string/z-algo.hpp" int main() { std::string s; std::cin >> s; const auto res = zalg(s); for(size_t i = 0; i < s.size(); ++i) { std::cout << res[i] << " \n"[i + 1 == s.size()]; } }
#line 1 "test/zalgo.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <iostream> #line 2 "C++/string/z-algo.hpp" #include <vector> std::vector<int> zalg(const std::string &s) { const int n = s.size(); int j = 0; std::vector<int> pre(n); for(int i = 1; i < n; ++i) { if(i + pre[i - j] < j + pre[j]) pre[i] = pre[i - j]; else { int k = std::max(0, j + pre[j] - i); while(i + k < n && s[k] == s[i + k]) ++k; pre[i] = k; j = i; } } pre.front() = n; return pre; } /** * @brief Z-Algorithm */ #line 4 "test/zalgo.test.cpp" int main() { std::string s; std::cin >> s; const auto res = zalg(s); for(size_t i = 0; i < s.size(); ++i) { std::cout << res[i] << " \n"[i + 1 == s.size()]; } }