Pagini recente » Cod sursa (job #2510441) | Cod sursa (job #1315035) | Cod sursa (job #110779) | Cod sursa (job #3224267) | Cod sursa (job #894536)
Cod sursa(job #894536)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SMAX=1000005;
int n,i,j,P[SMAX*2],l,r,N,maxr,center;
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; N++;}
for(i=1;i<=N-1;i++)
{
if(i<=maxr) P[i]=min(P[2*center-i],maxr-i+1);
l=i; r=i; l--; r++; l-=P[i]; r+=P[i];
while(l>=1 && r<=N && S[l]==S[r]) {P[i]+=2;l-=2;r+=2;}
r-=2; if(r>maxr) {maxr=r; center=i;} //printf("%d\n",maxr);
sol+=(P[i]+1)/2;
}
//for(i=1;i<=N-1;i++) printf("%d ",P[i]);
printf("%lld\n",sol);
return 0;
}