Pagini recente » Cod sursa (job #97880) | Cod sursa (job #746719) | Cod sursa (job #2868161) | Cod sursa (job #1190152) | Cod sursa (job #2040817)
#include<bits/stdc++.h>
#define Nmax 1000005
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int p[Nmax];
int pp[Nmax];
string s;
int main()
{
int center=0,rsh=-1,rad,i;
long long ans=0;
f>>s;
int n=s.size();
for(i=0;i<n;i++)
{
if(i<=rsh)
rad=min(p[center+rsh-i],rsh-i);
else rad=1;
while(i+rad<n and i-rad>=0 and s[i+rad]==s[i-rad])
++rad;
p[i]=rad;
if(i+rad-1>rsh)
{
center=i-rad;
rsh=i+rad-1;
}
}
center=0;
rsh=-1;
for(i=0;i<n;i++)
{
if(i<=rsh)
rad=min(pp[center+rsh-i+1],rsh-i+1)+1;
else rad=1;
while(i+rad-1<n and i-rad>=0 and s[i+rad-1]==s[i-rad])
++rad;
pp[i]=--rad;
if(i+rad-1 >rsh)
{
center=i-rad;
rsh=i+rad-1;
}
}
for(i=0;i<n;i++)
ans+=(1LL*(p[i]+pp[i]));
g<<ans;
return 0;
}