Pagini recente » Cod sursa (job #1647968) | Cod sursa (job #113865) | Cod sursa (job #2402767) | Cod sursa (job #2351044) | Cod sursa (job #2040819)
#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++)
{
rad=(i>rsh ? 1 : min(p[center+rsh-i],rsh-i)) ;
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++)
{
rad=(i>rsh ? 0 : min(pp[center+rsh-i+1],rsh-i+1))+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;
}