Cod sursa(job #2377119)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 8 martie 2019 21:55:27
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

char sir1[1000010],sir[2000010];
int d[2000010];

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    scanf("%s",sir1+1);
    int l=strlen(sir1+1),n=0;
    for(int i=1;i<=l;i++)
    {
        sir[++n]=sir1[i];
        sir[++n]='*';
    }
    n--;
    int lmax=0,poz=0;
    for(int i=1;i<=n;i++)
    {
        if(i+d[i]<poz+lmax) d[i]=min(poz+lmax-i,d[2*poz-i]);
        if(i+d[i]>=poz+lmax) while(i+d[i]<n && i-d[i]>1 && sir[i+d[i]+1]==sir[i-d[i]-1]) d[i]++;
        if(i+d[i]>poz+lmax) {lmax=d[i];poz=i;}
    }
    long long sol=0;
    for(int i=1;i<=n;i++)
        if(sir[i]!='*') sol+=d[i]/2+1;
        else sol+=d[i]/2+d[i]%2;
    printf("%lld",sol);
    return 0;
}