Cod sursa(job #3294659)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 27 aprilie 2025 00:09:02
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

const int MAXN = 1000000;

int len[2 * MAXN];

int main() {
  string s;
  fin >> s;
  string t = "";
  for(int i = 0; i < (int)s.size() - 1; i++) {
    t.push_back(s[i]);
    t.push_back('#');
  }
  t.push_back(s.back());
  s = t;
  
  int center = 0, maxr = -1;
  long long answer = 0;
  for(int i = 0; i < (int)s.size(); i++) {
    if(i < maxr) {
      int mirror = 2 * center - i; // oglinda in cealalta jumatate
      // se copiaza palindromul centrat in mirror invers la i
      len[i] = min(len[mirror], maxr - i);
    } else {
      len[i] = 0;
    }
    
    while(i - len[i] - 1 >= 0 && i + len[i] + 1 < (int)s.size() &&
          s[i - len[i] - 1] == s[i + len[i] + 1]) {
      len[i]++;
    }
    
    if(i + len[i] > maxr) {
      maxr = i + len[i];
      center = i;
    }
    
    answer += len[i] / 2 + (s[i] != '#');
  }
  
  fout << answer << "\n";
  return 0;
}