This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub crackersamdjam/Codebook
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include "../content/string/z_algorithm.h" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); string s; cin>>s; auto v = zed(s); v[0] = size(s); for(int i: v) cout<<i<<' '; }
#line 1 "tests/z_algorithm.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #line 1 "content/utils/template.h" /** * @brief My starter code */ #include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end()); #ifdef LOCAL template<typename T> void pr(T a){std::cerr<<a<<std::endl;} template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);} #else template<typename... Args> void pr(Args... args){} #endif using namespace std; using ll = long long; using pii = pair<int, int>; #line 3 "content/string/z_algorithm.h" /** * @brief Z Algorithm * @docs docs/z_algorithm.md */ vector<int> zed(string s){ int n = (int)size(s); 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 and 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 3 "tests/z_algorithm.test.cpp" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); string s; cin>>s; auto v = zed(s); v[0] = size(s); for(int i: v) cout<<i<<' '; }