Pagini recente » Borderou de evaluare (job #1036339) | Cod sursa (job #573692) | Cod sursa (job #2157851) | Cod sursa (job #214872) | Cod sursa (job #1883883)
#include <iostream>
#include <cstdio>
#include <string.h>
#define cout cerr
#define MAX 1000003 * 2
using namespace std;
char a[MAX],x;
int n=1,R,C;
int pal[MAX];
long long S;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
/*a[n++]='#';
while(!feof(stdin))
{
scanf("%c",&x);
if(x>='a' && x<='z')
{
a[n++]=x;
a[n++]='#';
}
}*/
scanf("%s",a+2);
n=strlen(a+2);
n=2*n+2;
pal[1]=0;
pal[2]=1;
C=2,R=3;
S=1;
for(int i=3;i<n;i++)
{
int ii=2*C-i;
if(pal[ii]+i<R)
pal[i]=pal[ii];
else
{
pal[i]=R-i;
if(pal[i]<0)
pal[i]=0;
}
//cout<<i<<" "<<C<<" "<<R<<" "<<pal[i]<<endl;
while(pal[i]+i+1<n && i-pal[i]-1>0)
if((pal[i]+i+1)%2==1)
pal[i]++;
else if(a[(i+pal[i]+1)/2+1]==a[(i-pal[i]-1)/2-1])
pal[i]++;
else break;
if(i+pal[i]>=R)
{
C=i;
R=pal[i]+i;
}
S+=(pal[i]+1)/2;
}
/*cout<<endl;
cout<<"# ";
for(int i=2;i<=n/2;i++)
cout<<a[i]<<" # ";
cout<<endl;
for(int i=1;i<n;i++)
cout<<pal[i]<<" ";
cout<<endl;*/
printf("%d",S);
return 0;
}