Pagini recente » Cod sursa (job #2094076) | Cod sursa (job #376850) | Cod sursa (job #2170208) | Cod sursa (job #3148504) | Cod sursa (job #1883706)
#include <iostream>
#include <cstdio>
#define cout cerr
#define MAX 200002
using namespace std;
char a[MAX],x;
int n=1,R,C;
int pal[MAX],S;
int main()
{
freopen("manacher.in","r",stdin);
freopen("manacher.out","w",stdout);
a[n++]='#';
while(!feof(stdin))
{
scanf("%c",&x);
if(x>='a' && x<='z')
{
a[n++]=x;
a[n++]='#';
}
}
pal[1]=0;
pal[2]=1;
C=1,R=1;
for(int i=3;i<n;i++)
{
int l=i-C;
int ii=2*C-i;
if(pal[ii]<R-i)
pal[i]=pal[ii];
else
{
pal[i]=0;
while(pal[i]+i+1<n && i-pal[i]-1>0
&& a[pal[i]+i+1]==a[i-pal[i]-1])
pal[i]++;
}
if(l>=R)
{
C=i;
R=pal[C];
}
//cout<<C<<" "<<R<<endl;
}
/*cout<<endl;
for(int i=1;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
for(int i=1;i<n;i++)
cout<<pal[i]<<" ";*/
for(int i=1;i<n;i++)
if(pal[i]>1)
S+=pal[i]-1;
else S+=pal[i];
//cout<<endl;
//cout<<S;
printf("%d",&S);
return 0;
}