Pagini recente » Cod sursa (job #962335) | Cod sursa (job #1604592) | Cod sursa (job #1760509) | Cod sursa (job #1119169) | Cod sursa (job #893484)
Cod sursa(job #893484)
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define min(a,b) a<b?a:b
int i,j,R,C,P[1000010],len;
long long SOL;
char S[1000100],*p;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf(" %s",S+1);
len=strlen(S+1);
C=0;R=0;
for(i=1;i<=len;i++)
{
j=2*C-i;
if(i<R)
P[i]=min(R-i,P[j]);
else P[i]=0;
while(S[i+P[i]+1]&&P[i]<i&&S[i+P[i]+1]==S[i-P[i]])P[i]++;
if(i+P[i]>R)
{
C=i;
R=i+P[i];
}
SOL+=P[i];
}
C=0;R=0;
memset(P,0,sizeof(P));
for(i=1;i<=len;i++)
{
j=2*C-i;
if(i<R)
P[i]=min(R-i,P[j]); else P[i]=0;
while(P[i]<i&&S[i+P[i]]&&S[i+P[i]]==S[i-P[i]])P[i]++;
if(i+P[i]>R)
{
C=i;R=i+P[i];
}
SOL+=P[i];
}
printf("%lld\n",SOL);
return 0;
}