Cod sursa(job #913387)

Utilizator simpleBereczki Cristian simple Data 13 martie 2013 13:40:15
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<string.h>
FILE *f=fopen("pscpld.in","r"),*g=fopen("pscpld.out","w");
char a[1000001],b[2000001];
int i,lung[2000001],poz=1,lungimepoz=1,n;
long long int nr;
int minimum(int a,int b)
{
    if(a<b) return a;
    return b;
}
int main()
{
fgets(a,1000001,f);
fclose(f);
n=strlen(a);
for(i=0;i<n;i++)
{
    b[2*i+1]=a[i];
    b[2*i]=' ';
}
nr=1;
n=2*n-1;
lung[0]=1;
lung[1]=1;
for(i=2;i<=n;i++)
{
    lung[i]=1;
    if(poz+lungimepoz-1>i)
    {
        lung[i]=minimum(poz+lungimepoz-i,lung[2*poz-i]);
    }
    while(i-lung[i]>0 && b[i-lung[i]]==b[i+lung[i]])
        {lung[i]++;
        }
    if(i%2)
    {
        nr+=(lung[i]+1)/2;
    }
    else
    {
        nr+=lung[i]/2;
    }
    if(poz+lungimepoz<i+lung[i]) poz=i;lungimepoz=lung[i];}
fprintf(g,"%d",nr);
fclose(g);
return 0;
}