Pagini recente » Cod sursa (job #80373) | Cod sursa (job #2297796) | Cod sursa (job #2197819) | Cod sursa (job #1595907) | Cod sursa (job #1757001)
#include <cstdio>
#include <cstring>
#include <cctype>
#define MAXN 1000000
using namespace std;
int raza[2*MAXN+5];
char v[2*MAXN+5]={'#'};
int main()
{
FILE *fin, *fout;
long long ans;
int n, x, r, i;
fin=fopen("pscpld.in", "r");
v[1]='*'; v[2]=fgetc(fin); n=2;
while(isalpha(v[n])){
v[++n]='*';
v[++n]=fgetc(fin);
}
v[n]='$'; --n;
fclose(fin);
x=2; raza[2]=1; ans=1LL;
for(i=3; i<n; i++){
if(x+raza[x]>=i)
if(i+raza[2*x-i]<=x+raza[x])
r=raza[2*x-i];
else
r=x+raza[x]-i;
else
r=0;
while(v[i+r]==v[i-r])
++r;
raza[i]=--r;
if(r+i>raza[x]+x)
x=i;
ans+=1LL*(raza[i]+1)/2;
}
fout=fopen("pscpld.out", "w");
fprintf(fout, "%lld\n", ans);
fclose(fout);
return 0;
}