Cod sursa(job #2979671)

Utilizator raresgherasaRares Gherasa raresgherasa Data 15 februarie 2023 18:35:09
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 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 s; fin >> s;
   s = "$" + s + "%";
   int l = 1, r = 1;
   int n = (int)s.size();
   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];
   }
   fout << ans;
}