Cod sursa(job #1786540)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 23 octombrie 2016 11:26:48
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

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

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