Cod sursa(job #1345023)

Utilizator ASTELOTudor Enescu ASTELO Data 17 februarie 2015 10:29:31
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<cstdio>
#include<cstring>
long long v[1000001],i,n,m,k,max=0,poz=0,j;
long long nr;
char s[1000001];
int main ()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(s);
n=strlen(s);
v[0]=0;
for(i=1;i<n;i++)
    {
    if(i>max)
        {
        for(j=i+1;j<n;j++)
            if(s[j]!=s[i-(j-i)])
                break;
        max=j-1;
        v[i]=max-i;
        poz=i;
        }
    else
        if(i<=max)
            {
            k=i-poz;
            if(k-v[k]>poz-v[poz])
                v[i]=v[k];
            else
                {
                for(j=max+1;j<n;j++)
                    if(s[j]!=s[i-(j-i)])
                        break;
                max=j-1;
                v[i]=max-i;
                poz=i;
                }
            }
    }
int nn=1;
for(i=1;i<n;i++)
    {
    if(s[i]==s[i-1])
        nn++;
    else
        {
        if(nn%2==1)
            nr+=(nn/2)*(nn/2+1);
        else
            nr+=(nn/2)*(nn/2+1)-nn/2;
        nn=1;
        }
    }
if(nn%2==1)
    nr+=(nn/2)*(nn/2+1);
else
    nr+=(nn/2)*(nn/2+1)-nn/2;
for(i=0;i<n;i++)
    nr+=v[i]+1;
printf("%lld",nr);
return 0;
}