This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes" #include <bits/extc++.h> using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; #include "../manacher.hpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); string s; cin >> s; auto ans = manacher(s); for (auto v : ans) cout << v - 1 << ' '; }
#line 1 "strings/test/Enumerate_Palindromes.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/enumerate_palindromes" #include <bits/extc++.h> using namespace std; using namespace __gnu_cxx; using namespace __gnu_pbds; #line 1 "strings/manacher.hpp" vector<int> manacher_odd(string s) { int n = s.size(); s = "$" + s + "^"; vector<int> p(n + 2); int l = 1, r = 1; for (int i = 1; i <= n; i++) { p[i] = max(0, min(r - i, p[l + (r - i)])); while (s[i - p[i]] == s[i + p[i]]) { p[i]++; } if (i + p[i] > r) { l = i - p[i], r = i + p[i]; } } return vector<int>(begin(p) + 1, end(p) - 1); } vector<int> manacher(const string &s) { string t; for (auto c : s) { t += string("#") + c; } auto res = manacher_odd(t + "#"); return vector<int>(begin(res) + 1, end(res) - 1); } #line 10 "strings/test/Enumerate_Palindromes.test.cpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); string s; cin >> s; auto ans = manacher(s); for (auto v : ans) cout << v - 1 << ' '; }