Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- #include <cstring>
- #include <map>
- using namespace std;
- typedef int ll;
- ll manachers_algorithm(const string & s) {
- ll res = 0;
- string t = "^";
- for(char c: s) {
- t += "#";
- t += c;
- }
- t += "#$";
- int n = (int) t.length();
- vector<int> P(n, 0);
- int C = 0, R = 0;
- int max_length = 0, center_idx = 0;
- for(int i = 1; i < n - 1; i++) {
- int i_mirror = 2 * C - i;
- if(R > i) {
- P[i] = min(R - i, P[i_mirror]);
- }
- while(t[i + 1 + P[i]] == t[i - 1 - P[i]]) {
- P[i]++;
- }
- if(i + P[i] > R) {
- C = i;
- R = i + P[i];
- }
- if(P[i] > max_length) {
- max_length = P[i];
- center_idx = i;
- }
- res += (P[i] + 1) / 2;
- }
- return res;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- string s;
- cin >> s;
- ll res = manachers_algorithm(s);
- int n = (int) s.size();
- for(int i = 0; i < n / 2; i++) {
- char orig = s[i];
- for(char c = 'a'; c <= 'z'; c++) {
- if(c == orig) continue;
- s[i] = c;
- res = max(res, manachers_algorithm(s));
- }
- s[i] = orig;
- }
- cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment