Pagini recente » Cod sursa (job #159024) | Cod sursa (job #462766) | Cod sursa (job #2366029) | Cod sursa (job #2919708) | Cod sursa (job #910870)
Cod sursa(job #910870)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMax 1000010
using namespace std;
const char IN[]="pscpld.in",OUT[]="pscpld.out";
int N,Rez;
int T[2*NMax];
char s[2*NMax];
int main()
{
int l,i,j,p;
freopen(IN,"r",stdin);
scanf("%s",s+1);
fclose(stdin);
N=strlen(s+1);
for (i=N;i>0;--i)
s[2*i-1]=s[i],s[2*i-2]='#';
p=0,l=0;T[0]=1;
for (i=1,l=0;i<=2*N;++i){
T[i]=1;
if (i<=l){
T[i]=min(l-i+1,T[2*p-l]);
}
for (j=i+T[i];j<=N && s[j]==s[2*i-j];)
++j;
--j;
T[i]=j-i+1;
if (i+T[i]>l)
p=i,l=i+T[i]-1;
if (i%2) Rez+=T[i]/2;
else Rez+=(T[i]+1)/2;
}
freopen(OUT,"w",stdout);
printf("%d\n",Rez);
fclose(stdout);
return 0;
}