Pagini recente » Cod sursa (job #211988) | Cod sursa (job #59430) | Cod sursa (job #1493704) | Cod sursa (job #704702) | Cod sursa (job #2784453)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int i,nr,center,sum,n,st,dr,radius,dp[2000005];
void pal(string s)
{
n=s.size();
string a;a[nr++]='*';
for(i=0; i<n; i++)
{
a[nr++]=s[i];
a[nr++]='*';
}
n=nr;
dp[0]=1;
center=0;
radius=1;
for(i=1; i<=nr; i++)
{
if(i>=center+radius)
{
st=i-1;
dr=i+1;
while(a[st]==a[dr]&&st>=0&&dr<nr)
{
st--;
dr++;
}
center=i;
radius=i-st-1;
dp[i]=radius;
}
else
{
if(i-radius-dp[i-radius]<=center-radius)
{
st=i-1;
dr=i+1;
while(a[st]==a[dr]&&st>=0&&dr<nr)
{
st--;
dr++;
}
center=i;
radius=i-st-1;
dp[i]=radius;
}
else dp[i]=dp[i-radius];
}
}
for(i=1; i<nr; i++)sum+=(dp[i]+1)/2;
}
int main()
{
string s;
fin>>s;
pal(s);fout<<sum;
return 0;
}