Pagini recente » Cod sursa (job #1327264) | Cod sursa (job #1235222) | Cod sursa (job #1247738) | Cod sursa (job #1996849) | Cod sursa (job #721700)
Cod sursa(job #721700)
#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;
}