Pagini recente » Cod sursa (job #289908) | Cod sursa (job #2237508) | Cod sursa (job #2260236) | Cod sursa (job #1225762) | Cod sursa (job #2575395)
#include<bits/stdc++.h>
using namespace std;
int l,r;
const int maxN=(1e6)+5;
char s[maxN];
int k,odd[maxN],even[maxN];
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
l=0;
r=-1;
scanf("%s",s);
int n=strlen(s);
for(int i=0;i<n;i++)
{
if(i>r) k=1;
else k=min(r-i,odd[l+r-i]);
while((i-k)>=0 && (i+k)<=n && s[i+k]==s[i-k]) k++;
odd[i]=k;
k--;
if(i+k>r)
{
r=i+k;
l=i-k;
}
}
l=0;
r=-1;
for(int i=0;i<n;i++)
{
if(i>r) k=1;
else k=min(r-i+1,even[l+r-i+1]);
while((i-k)>=0 && (i+k-1)<=n && s[i-k]==s[i+k-1]) k++;
k--;
even[i]=k;
if((i+k-1)>r)
{
r=i+k-1;
l=i-k;
}
}
long long sol=0;
for(int i=0;i<n;i++)
sol=sol+1LL*(odd[i]+even[i]);
printf("%lld\n",sol);
return 0;
}