Pagini recente » Cod sursa (job #931784) | Cod sursa (job #1421851) | Cod sursa (job #1187840) | Cod sursa (job #1057389) | Cod sursa (job #1857925)
#include <fstream>
#include<cstring>
using namespace std;
ifstream cin ("message.in");
ofstream cout ("message.out");
char s[2000001],t[1000001];
int n=-1,centru,righ,maxim,pmaxim,l[2000001];
void read ()
{ int i=0;
cin.getline(t,1000001);
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-1,i+c+1,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;
}