Josif_tepe

Untitled

Aug 30th, 2026
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cstring>
  7. #include <map>
  8. using namespace std;
  9. typedef int ll;
  10.  
  11. ll manachers_algorithm(const string & s) {
  12.     ll res = 0;
  13.      
  14.     string t = "^";
  15.     for(char c: s) {
  16.         t += "#";
  17.         t += c;
  18.     }
  19.     t += "#$";
  20.      
  21.     int n = (int) t.length();
  22.     vector<int> P(n, 0);
  23.     int C = 0, R = 0;
  24.     int max_length = 0, center_idx = 0;
  25.      
  26.     for(int i = 1; i < n - 1; i++) {
  27.         int i_mirror = 2 * C - i;
  28.          
  29.         if(R > i) {
  30.             P[i] = min(R - i, P[i_mirror]);
  31.         }
  32.          
  33.         while(t[i + 1 + P[i]] == t[i - 1 - P[i]]) {
  34.             P[i]++;
  35.         }
  36.          
  37.         if(i + P[i] > R) {
  38.             C = i;
  39.             R = i + P[i];
  40.         }
  41.          
  42.         if(P[i] > max_length) {
  43.             max_length = P[i];
  44.             center_idx = i;
  45.         }
  46.          
  47.         res += (P[i] + 1) / 2;
  48.     }
  49.     return res;
  50. }
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(NULL);
  54.      
  55.     string s;
  56.     cin >> s;
  57.  
  58.     ll res = manachers_algorithm(s);
  59.     int n = (int) s.size();
  60.      
  61.     for(int i = 0; i < n / 2; i++) {
  62.         char orig = s[i];
  63.         for(char c = 'a'; c <= 'z'; c++) {
  64.             if(c == orig) continue;
  65.             s[i] = c;
  66.             res = max(res, manachers_algorithm(s));
  67.         }
  68.         s[i] = orig;
  69.     }
  70.      
  71.     cout << res;
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment