Pagini recente » Cod sursa (job #711765) | Cod sursa (job #1862735) | Cod sursa (job #1627489) | Cod sursa (job #2818070) | Cod sursa (job #1857916)
#include <fstream>
#include<cstring>
using namespace std;
ifstream cin ("pscpld.in");
ofstream cout ("pscpld.out");
char s[2000001],t[1000001];
int n=0,centru,righ,maxim,pmaxim,l[2000001];
void read ()
{ int i=0;
cin>>t;
while(t[i]!=0)
{
s[++n]='#';
s[++n]=t[i]; i++;
}
s[++n]='#';
}
int expand (int aa,int bb,int poz)
{
while(3>2 && aa>=0 && bb<=n)
{
if(s[aa]!=s[bb]) return poz-aa-1;
aa--; ++bb;
}
return poz-aa-1;
}
void solve_here ()
{
centru=0; righ=0;
for(int i=1;i<=n;i++)
{
if(i>righ) l[i]=expand(i,i,i);
else
{
int c=min(l[centru-i+centru],righ-centru);
l[i]=expand(i-c,i+c,i);
}
if(l[i]+i>righ) righ=l[i]+i,centru=i;
}
}
void write ()
{ int sum=0;
for(int i=0;i<n;i++)
{
sum=sum+(l[i]+1)/2;
}
cout<<sum;
}
int main()
{
read();
solve_here();
write();
cin.close();
cout.close();
return 0;
}