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/enumerate_palindromes" #include "../content/string/manacher.h" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); string s; cin>>s; auto [a, b] = manacher(s); for(int i = 0; i < (int)size(s)-1; i++){ cout<<a[i]*2-1<<' '<<b[i+1]*2<<' '; } cout<<a.back()<<'\n'; }
#line 1 "tests/manacher.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes" #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/manacher.h" /** * @brief Manacher's Algorithm * @docs docs/manacher.md */ pair<vector<int>, vector<int>> manacher(string s){ s = "@"+s+"#"; int n = (int)size(s); vector<int> p1(n), p2(n); //radii of palindromes (1 odd, 2 even length) for(int i = 1, mx = 0, p = 0; i < n-1; i++){ p1[i] = (i >= mx) ? 1 : min(mx-i, p1[p*2-i]); while(s[i-p1[i]] == s[i+p1[i]]) p1[i]++; if(i+p1[i] > mx) mx = i+p1[i], p = i; } for(int i = 1, mx = 0, p = 0; i < n-1; i++){ p2[i] = (i >= mx) ? 0 : min(mx-i, p2[p*2-i+2]); while(s[i-p2[i]-1] == s[i+p2[i]]) p2[i]++; if(i+p2[i] > mx) mx = i+p2[i], p = i-1; } p1.erase(p1.begin()); p2.erase(p2.begin()); p1.pop_back(); p2.pop_back(); return {p1, p2}; } #line 3 "tests/manacher.test.cpp" int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); string s; cin>>s; auto [a, b] = manacher(s); for(int i = 0; i < (int)size(s)-1; i++){ cout<<a[i]*2-1<<' '<<b[i+1]*2<<' '; } cout<<a.back()<<'\n'; }