Pagini recente » Cod sursa (job #1547637) | Cod sursa (job #2093655) | Cod sursa (job #2867101) | Cod sursa (job #957109) | Cod sursa (job #894421)
Cod sursa(job #894421)
#include<cstdio>
#include<cstring>
using namespace std;
const int SMAX=1000005;
int n,i,j,P[SMAX*2],M[SMAX*2],l,r,N;
long long sol;
char a[SMAX],S[SMAX*2];
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",a+1); n=strlen(a+1);
for(i=1;i<=n;i++)
{
S[++N]=a[i]; P[N]=1;
S[++N]=' ';
}
for(i=1;i<=N-1;i++)
{
if(M[i]) P[i]=P[2*M[i]-i];
l=i; r=i; l--; r++; l-=P[i]; r+=P[i];
while(l>=1 && r<=N && S[l]==S[r]) P[i]+=2,M[r]=M[r-1]=i,l-=2,r+=2;
sol+=(P[i]+1)/2;
}
//for(i=1;i<=N-1;i++) printf("%d ",P[i]);
printf("%lld\n",sol);
return 0;
}