Pagini recente » tema | Cod sursa (job #2731023) | Cod sursa (job #747308) | Cod sursa (job #1076497) | Cod sursa (job #1960573)
#include <bits/stdc++.h>
#define MAXN 1000002
int len[2*MAXN+1];
char v[2*MAXN+1];
int main(){
FILE*fi,*fout;
int i,n,k;
char ch;
fi=fopen("pscpld.in" ,"r");
fout=fopen("pscpld.out" ,"w");
ch=fgetc(fi);
n=0;
while(isalpha(ch)){
v[++n]='*';
v[++n]=ch;
ch=fgetc(fi);
}
v[n+1]='*';
k=0;
for(i=1;i<=n+1;i++){
if(k+len[k]<=i)
len[i]=1;
else
len[i]=std::min(len[2*k-i],k+len[k]-i);
while(i-len[i]>0&&i+len[i]<=n+1&&v[i-len[i]]==v[i+len[i]])
len[i]++;
if(i+len[i]>k+len[k])
k=i;
}
long long ans=0;
for(i=1;i<=n+1;i++)
ans+=len[i]/2;
fprintf(fout,"%lld" ,ans);
fclose(fi);
fclose(fout);
return 0;
}