This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <bits/stdc++.h> using namespace std; #include "../zfunc.h" int32_t main() { ios::sync_with_stdio(0); cin.tie(0); string s; cin >> s; for (auto x : zfunc(s)) { cout << x << ' '; } cout << '\n'; return 0; }
#line 1 "String/tests/zfunc.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm" #include <bits/stdc++.h> using namespace std; #line 1 "String/zfunc.h" // z[i] = length of longest common prefix of s[0..N] and s[i..N] // // Tested: // - https://judge.yosupo.jp/problem/zalgorithm // - (string matching) https://oj.vnoi.info/problem/substr // Z-func {{{ vector<int> zfunc(const string& s) { int n = (int) s.length(); vector<int> z(n); z[0] = 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; } // }}} // Examples: // Find all occurrences of p in t /** string s = p + "_" + t; auto z = zfunc(s); REP(i,SZ(t)) { if (z[i + SZ(p) + 1] == SZ(p)) { cout << 1+i << ' '; } } cout << endl; */ #line 7 "String/tests/zfunc.test.cpp" int32_t main() { ios::sync_with_stdio(0); cin.tie(0); string s; cin >> s; for (auto x : zfunc(s)) { cout << x << ' '; } cout << '\n'; return 0; }