Cod sursa(job #2960477)

Utilizator ezluciPirtac Eduard ezluci Data 4 ianuarie 2023 14:36:31
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;

const int nMAX = 1e6;

int n;
char s[2*nMAX + 1];
int rz[2*nMAX + 1];

int main()
{
   freopen("pscpld.in", "r", stdin);
   freopen("pscpld.out", "w", stdout);
   char c;

   while (isalpha(c = getchar_unlocked()))
      s[n++] = '.',  s[n++] = c;
   s[n++] = ',';

   ll ans = 0;
   int l = 0, r = 0;
   for (int i = 1; i < n-1; ++i)
   {
      if (i <= r)
         rz[i] = min(rz[l+r-i], r-i);
      
      while (s[i - rz[i] - 1] == s[i + rz[i] + 1])
         rz[i] ++;
      
      if (i + rz[i] > r)
         l = i - rz[i],
         r = i + rz[i];
      
      if (s[i] == '.')
         ans += (rz[i]+1) / 2;
      else
         ans += rz[i] / 2 + 1;
   }

   cout << ans;
}