Pagini recente » Cod sursa (job #253263) | Cod sursa (job #1230980) | Cod sursa (job #1021131) | Cod sursa (job #638523) | Cod sursa (job #910883)
Cod sursa(job #910883)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMax 1000010
using namespace std;
typedef long long ll;
const char IN[]="pscpld.in",OUT[]="pscpld.out";
int N;ll 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]='#';
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-i]);
for (j=i+T[i];2*i-j>=0 && j<=2*N && s[j]==s[2*i-j];)
++j;
--j;
T[i]=j-i+1;
if (i+T[i]-1>l)
p=i,
l=i+T[i]-1;
if (i%2) Rez+=(T[i]+1)/2;
else Rez+=T[i]/2;
}
freopen(OUT,"w",stdout);
printf("%lld\n",Rez);
fclose(stdout);
return 0;
}