Pagini recente » Cod sursa (job #109631) | Cod sursa (job #3265840) | Cod sursa (job #282589) | Cod sursa (job #2476536) | Cod sursa (job #1883730)
#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;
S=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];
}
S+=(pal[i]+1)/2;
}
printf("%d",S);
return 0;
}