Cod sursa(job #2979682)

Utilizator raresgherasaRares Gherasa raresgherasa Data 15 februarie 2023 18:52:04
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 1e6 + 5;

int pal[kN];
long long ans = 0;

int main(){
   ios_base::sync_with_stdio(false);

   string t; fin >> t;
   string s = "#";
   for (char x : t){
      s += "$";
      s += x;
   }
   s += "$%";
   int n = (int)s.size() - 2;
   int l = 1, r = 1;
   for (int i = 1; i <= n; i++){
      pal[i] = max(0, min(r - i, pal[l + (r - i)]));
      while (s[i + pal[i]] == s[i - pal[i]]){
         ++pal[i];
      }
      if (i + pal[i] > r){
         l = i - pal[i];
         r = i + pal[i];
      }
      ans += pal[i] / 2;
   }
   fout << ans;
}