Pagini recente » Cod sursa (job #486392) | Cod sursa (job #521729) | Cod sursa (job #773809) | Cod sursa (job #2366450) | Cod sursa (job #1857936)
#include <fstream>
#include<cstring>
using namespace std;
ifstream cin ("pscpld.in");
ofstream cout ("pscpld.out");
char t[1000010],s[2000011];
int n=-1,r,c,l[2000012],poz,rez;
void read ()
{
cin>>t;
int m=strlen(t);
for(int i=0;i<m;i++)
s[++n]='#',s[++n]=t[i];
s[++n]='#';
}
void expand (int st,int dr)
{
while(st>=0 && dr<=n && s[st]==s[dr])
{
l[poz]++;
st--; dr++;
}
}
void solve ()
{
c=0; r=0;
for(int i=1;i<=n;i++)
{
if(i<=r) l[i]=l[2*c-i]; poz=i;
expand(i-l[i]-1,i+l[i]+1);
if(i+l[i]>r) r=i+l[i],c=i;
rez=rez+(l[i]+1)/2;
}
}
void write ()
{
cout<<rez<<"\n";
}
int main()
{
read();
solve();
write();
cin.close();
cout.close();
return 0;
}