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/enumerate_palindromes" #include <bits/stdc++.h> using namespace std; #include "../manacher.h" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) #define SZ(x) ((int)(x).size()) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); string s; cin >> s; auto [even, odd] = manacher(s); REP(i,SZ(s)) { cout << odd[i] << ' '; if (i+1 < SZ(s)) cout << even[i] << ' '; } cout << endl; return 0; }
#line 1 "String/tests/manacher.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes" #include <bits/stdc++.h> using namespace std; #line 1 "String/manacher.h" // Manacher {{{ // Return <even_len, odd_len> // - even_len[i] = length of longest palindrome centered at [i, i+1] // - odd_len[i] = length of longest palindrome centered at i // // Tested: // - https://judge.yosupo.jp/problem/enumerate_palindromes // - https://oj.vnoi.info/problem/paliny std::array<vector<int>, 2> manacher(const string& s) { int n = s.size(); std::array res = {vector<int> (n+1, 0), vector<int> (n, 0)}; for (int z = 0; z < 2; z++) { for (int i = 0, l = 0, r = 0; i < n; i++) { int t = r - i + !z; if (i < r) res[z][i] = min(t, res[z][l + t]); int l2 = i - res[z][i], r2 = i + res[z][i] - !z; while (l2 && r2 + 1 < n && s[l2 - 1] == s[r2 + 1]) { ++res[z][i]; --l2; ++r2; } if (r2 > r) { l = l2; r = r2; } } for (int i = 0; i < n; i++) { res[z][i] = 2*res[z][i] + z; } } res[0].erase(res[0].begin(), res[0].begin() + 1); res[0].pop_back(); return res; } // }}} #line 7 "String/tests/manacher.test.cpp" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) #define SZ(x) ((int)(x).size()) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); string s; cin >> s; auto [even, odd] = manacher(s); REP(i,SZ(s)) { cout << odd[i] << ' '; if (i+1 < SZ(s)) cout << even[i] << ' '; } cout << endl; return 0; }