Cod sursa(job #721700)

Utilizator bacilaBacila Emilian bacila Data 24 martie 2012 00:01:50
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
using namespace std;
int n,d[1000005],dd[1000005];
long long sum;
char a[1000005];
int expand(int i,int j)
{int k=0;
while(a[i-k]==a[j+k]&&a[i-k])
k++;
return k;}
void odd()
{int i,r=0,p=0;
for(i=1;i<=n;i++)
{
if(i<=r)
dd[i]=min(dd[p-(i-p)],r-i);
dd[i]+=expand(i-dd[i],i+dd[i]);
if(dd[i]+i>r)
{p=i;r=p+dd[i];
}
sum+=dd[i];
}
     }
void even()
{int i,r=0,p=0;
for(i=1;i<=n;i++)
if(a[i]==a[i+1]){
if(i<r)
d[i]=min(d[p-(i-p)],r-i-1);
d[i]+=expand(i-d[i],i+d[i]+1);
if(d[i]+i+1>r)
{p=i;r=p+1+d[i];
}
sum+=d[i];
}
     }
int main ()
{ifstream f("pscpld.in");
 ofstream g("pscpld.out");
 f>>(a+1);
 n=strlen(a+1);
 even();
odd();
g<<sum;
 f.close(); g.close();
return 0;
}