Cod sursa(job #3305958)

Utilizator Maryy_1369Gociu Maria Anastasia Maryy_1369 Data 6 august 2025 11:12:53
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int mana[2000004];
int main(){
   string x1,s;
   cin>>x1;
   s="##";
   for(int i=0;i<x1.size();i++){
      s+=x1[i];
      s+='#';
   }
   int bs=0;
   for(int i=1;i<s.size();i++){
      if(bs+mana[bs]>=i){
         mana[i]=min( mana[bs-(i-bs)], bs+mana[bs]-i);
         while(i+mana[i]+1<s.size() && i-mana[i]-1>=1 && s[i+mana[i]+1]== s[i-mana[i]-1]){
            mana[i]++;
         }
         if(i+mana[i]>= bs+mana[bs])bs=i;
      }
      else{
        mana[i]=0;
        while(i+mana[i]+1<s.size() && i-mana[i]-1>=1 && s[i+mana[i]+1]==s[i-mana[i]-1]){
            mana[i]++;
        }
        bs=i;
      }
   }

   long long cnt=0;
   for(int i=1;i<s.size();i++){
      cnt+= (mana[i]+1)/2;
   }
   cout<<cnt;
}