Pagini recente » Cod sursa (job #72373) | Cod sursa (job #1250536) | Cod sursa (job #2131528) | Cod sursa (job #236112) | Cod sursa (job #2958899)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
char s[1000001],q[2000010];
int rz[2000010];
int n,l,r;
int main()
{
cin>>s;
l=-1;
r=-1;
q[n++]='#';
for(int i=0;s[i]!='\0';i++)
{
q[n++]=s[i];
q[n++]='#';
}
q[n++]='\0';
for(int i=0;i<n;i++)
{
if(i>r)
rz[i]=0;
else
rz[i]=min(r-i,rz[l+r-i]);
while(i-rz[i]>=0 && q[i-rz[i]]==q[i+rz[i]])
rz[i]++;
rz[i]--;
if(i+rz[i]>r)
{
r=i+rz[i];
l=i-rz[i];
}
}
long long sum=0;
for(int i=0;i<n;i++)
{
sum=sum+(rz[i]+1)/2;
}
cout<<sum;
return 0;
}