Untitled
c_cpp
a month ago
1.8 kB
2
Indexable
Never
/// Manacher - O(N) #include <bits/stdc++.h> using namespace std; 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(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); } // int main() { // string p = "abababc"; // vector<int> manacher_ = manacher(p); // for(int v : manacher_) { // cout<<v<<' '; // } // cout<<'\n'; // } int main() { string p; cin>>p; vector<int> manacher_ = manacher(p); int ma = 0, pos; for(int i = 0; i < (int)manacher_.size(); ++i) { const int v = manacher_[i]; if(v > ma) { ma = v, pos = i - (i+1)/2; } } --ma; string ans = ""; const int aux = ma / 2; for(int i = max(pos - aux, 0); i <= pos - 1; ++i) { ans += p[i]; } ans += p[pos]; for(int i = pos + 1; i <= min((int)p.size(), pos + aux); ++i) { ans += p[i]; } const int sz = (int)ans.size(); int i, j; for(i = 0, j = sz-1; ans[i] == ans[j] && i < j; ++i, --j); if(i < j) { for(i = 0, j = sz-2; ans[i] == ans[j] && i < j; ++i, --j); if(i >= j) { ans.pop_back(); cout<<ans<<'\n'; } else { for(int i = 1; i < sz; ++i) cout<<ans[i]; cout<<'\n'; } } else cout<<ans<<'\n'; }