Pagini recente » Cod sursa (job #111573) | Cod sursa (job #215447) | Cod sursa (job #2475893) | Cod sursa (job #2838166) | Cod sursa (job #1752417)
#include<bits/stdc++.h>
using namespace std;
int d1[1000005],d2[1000005],i,n,k,l,r;
long long rs;
string s;
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
getline(cin,s); n=s.length();
for(r=l=-1,i=0;i<n;++i)
{
k=(i>r) ? 1:min(d1[l+r-i],r-i+1);
while(i+k<n && i-k>=0 && s[i+k]==s[i-k]) ++k;
d1[i]=k--;
if(i+k>r) l=i-k,r=i+k;
}
for(r=l=-1,i=0;i<n;++i)
{
k=(i>r) ? 0:min(d2[l+r-i+1],r-i+1);
while(i+k<n && i-k-1>=0 && s[i+k]==s[i-k-1]) ++k;
d2[i]=k;
if(i+k-1>r) l=i-k,r=i+k-1;
}
for(i=0;i<n;++i) rs+=d1[i]+d2[i];
cout<<rs<<'\n';
return 0;
}