Pagini recente » Cod sursa (job #701168) | Cod sursa (job #1096619) | Cod sursa (job #62350) | Cod sursa (job #857738) | Cod sursa (job #1003842)
#include<fstream>
#include<string>
#include<algorithm>
using namespace std;
string in,s;
int p[2000005];
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
cin>>in;
s="+";
for(int i=0;i<(int)in.size();i++)
{
s+='#';
s+=in[i];
}
s+="#-";
int c=0,r=0;
for(int i=1;i<(int)s.size()-1;i++)
{
int j=2*c-i;
if(i<r)
p[i]=min(r-i,p[j]);
else
p[i]=0;
while(i+p[i]+1<(int)s.size() && i-p[i]-1>=0 && s[i+p[i]+1]==s[i-p[i]-1])
p[i]++;
if(i+p[i]>r)
{
c=i;
r=i+p[i];
}
}
int ans=0;
for(int i=1;i<(int)s.size()-1;i++)
ans+=(p[i]+1)/2;
cout<<ans<<endl;
return 0;
}