Pagini recente » Cod sursa (job #148864) | Cod sursa (job #1716656) | Cod sursa (job #1336129)
#include <stdio.h>
#define MAXN 1000000
char t[2*MAXN+3];
int p[2*MAXN+2];
int main(){
long long ans;
int n, c, r, i, j;
char ch;
FILE *fin, *fout;
fin=fopen("pscpld.in", "r");
fout=fopen("pscpld.out", "w");
t[0]='^';
n=1;
ch=fgetc(fin);
while(ch!='\n'){
t[n++]='#';
t[n++]=ch;
ch=fgetc(fin);
}
t[n]='#';
t[n+1]='$';
ans=0;
c=0;
r=0;
for(i=1; i<=n; i++){
j=2*c-i;
if(r>i){
if(p[j]<=r-i){
p[i]=p[j];
}else{
p[i]=r-i;
}
}
while(t[i+p[i]+1]==t[i-p[i]-1]){
p[i]++;
}
if(i+p[i]>r){
c=i;
r=i+p[i];
}
ans+=(p[i]+1)/2;
}
fprintf(fout, "%lld\n", ans);
fclose(fin);
fclose(fout);
return 0;
}