Cod sursa(job #3263614)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 15 decembrie 2024 15:49:40
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

int manacher[1000001];

int main()
{
    int i,sum=0,best;
    string s,aux;
    cin>>aux;
    for(i=0;i<aux.size();i++){
        s+='$';s+=aux[i];
    }s+='$';
    best=-1;
    for(i=0;i<s.size();i++){
        if(best!=-1 && best+manacher[best]-1>=i){
            manacher[i]=min(best+manacher[best]-i,manacher[2*best-i]);
        }
        while(i+manacher[i]<s.size() && i-manacher[i]>=0 && s[i+manacher[i]]==s[i-manacher[i]])
            manacher[i]++;
        if(best==-1 || i+manacher[i]-1>best+manacher[best]-1)
            best=i;
    }
    for(i=0;i<s.size();i++){
        if(manacher[i]){
            sum+=manacher[i]/2;
        }
    }
    cout<<sum;
    return 0;
}