Cod sursa(job #960503)

Utilizator predatorGigi Valoare predator Data 10 iunie 2013 16:55:24
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<fstream>
#include<cstring>
#define NM 1000100
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int D[NM],i,dr,rig,lef,n,p,ii;
long long S;
char s[NM];
int main ()
{
    f>>(s+1);
    n=strlen(s+1);
    for(i=1;i<=n;++i)
    {
        if(dr>i)
        {
            ii=p-(i-p);
            if(D[ii]/2+i<dr)
                D[i]=D[ii];
            else
            {
                lef=i-D[ii]/2;
                rig=i+D[ii]/2;
                while(rig>n)
                    rig--,lef++;
                while(s[lef]==s[rig]&&lef&&rig<=n)
                {
                    lef--;
                    rig++;
                }
                lef++;
                rig--;
                D[i]=rig-lef+1;
                p=i;
                dr=rig;
            }
        }
        else
        {
            lef=rig=i;
            while(s[lef]==s[rig]&&lef)
            {
                lef--;
                rig++;
            }
            lef++;
            rig--;
            D[i]=rig-lef+1;
            p=i;
            dr=rig;
        }
    }
    for(i=1;i<=n;++i)
    {
        S+=(D[i]+1)/2;
        D[i]=0;
    }
    dr=p=0;
    for(i=1;i<n;++i)
    {
        if(dr>i)
        {
            ii=p-(i-p);
            if(D[ii]/2+i<dr)
                D[i]=D[ii];
            else
            {
                lef=i-(D[ii]-1)/2;
                rig=i+D[ii]/2;
                while(rig>n)
                    rig--,lef++;
                while(s[lef]==s[rig]&&lef&&rig<=n)
                {
                    lef--;
                    rig++;
                }
                lef++;
                rig--;
                D[i]=rig-lef+1;
                p=i;
                dr=rig;
            }
        }
        else
        {
            lef=i;
            rig=i+1;
            if(s[lef]!=s[rig])
                continue;
            else
            {
                while(s[lef]==s[rig])
                {
                    lef--;
                    rig++;
                }
                lef++;
                rig--;
            }
            D[i]=rig-lef+1;
            p=i;
            dr=rig;
        }
    }
    for(i=1;i<n;++i)
        S+=D[i]/2;
    g<<S;
    return 0;
}