Cod sursa(job #2795415)

Utilizator Vlad_AnicaAnica-Popa Vlad-Ioan Vlad_Anica Data 6 noiembrie 2021 12:22:31
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

char sh[1000005],s[2000010];
int p;
int P[2000010];

void addH(){
    int l=strlen(sh),j=0;
    for(int i=0;i<l;i++){
        s[j++]='#';
        s[j++]=sh[i];
    }
    s[j++]='#';
    s[j]=0;
    p=j;
}

int main()
{
    f.getline(sh,1000005);
    addH();
    int R=0,C=0,si=0;
    for(int i=1;i<p;i++){
        si=C-(i-C);
        if(i<=R) P[i]=min(R-i,P[si]);
        while(i+1+P[i]<p && i-1-P[i]>=0 && s[i+1+P[i]]==s[i-1-P[i]]){
            P[i]++;
        }
        if(i+P[i]>R){
            R=i+P[i];
            C=i;
        }
    }
    long long h=0;
    for(int i=0;i<p;i++)
        h=h+P[i]/2+P[i]%2;
    g<<h;
}