Cod sursa(job #2774897)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 septembrie 2021 13:47:07
Problema PScPld Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<stdio.h>
#include<string.h>
int n,d[2000010],i,b;
char v[2000010];
long long s;
int main()
{
    freopen("pscpld.in","r",stdin),freopen("pscpld.out","w",stdout),scanf("%s",v+1),n=strlen(v+1);
    for(i=2*n+1;i;--i)
        v[i]=i%2?'#':v[i/2];
    for(n=2*n+1,i=1;i<=n;++i) {
        if(b+d[b]>=i)
            d[i]=(b+d[b]-i>d[2*b-i])?d[2*b-i]:(b+d[b]-i);
        for(;i-d[i]>1&&i+d[i]+1<=n&&v[i-d[i]-1]==v[i+d[i]+1];++d[i]);
        if(i+d[i]>=b+d[b])
            b=i;
    }
    for(i=1;i<=n;++i)
        s+=(i%2?(d[i]/2):(d[i]+1)/2);
    printf("%lld",s);
    return 0;
}