Cod sursa(job #960550)

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