Pagini recente » Cod sursa (job #1508947) | Cod sursa (job #698376) | Cod sursa (job #1986249) | Cod sursa (job #1935632) | Cod sursa (job #485468)
Cod sursa(job #485468)
#include <cstdio>
#include <cstring>
#define MAXLIM 1000020
using namespace std;
int N;
char S[MAXLIM*2];
char S2[MAXLIM];
int ext[MAXLIM];
int main(){
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
fgets(S2+1,MAXLIM,stdin);
N=strlen(S2+1);
while (S2[N]<'a' || S2[N]>'z') --N;
fclose(stdin);
int N2=0;
for (int i=1;i<N;++i){
++N2;
S[N2]=S2[i];
++N2;
S[N2]='*';
}
++N2;
S[N2]=S2[N];
N=N2;
long long csum=1;
int lowint=1;
int highint=1;
ext[1]=1;
for (int i=2;i<=N;++i)
if (i>highint){
int cst=i-1;
int cdr=i+1;
while (cdr<=N && cst>=1 && S[cst]==S[cdr]){
--cst;
++cdr;
}
++cst;
--cdr;
ext[i]=i-cst+1;
if (S[i]=='*') csum+=ext[i]/2; else csum+=ext[i]/2+ext[i]%2;
if (cdr>highint){
lowint=cst;
highint=cdr;
}
} else {
int j=lowint+highint-i;
ext[i]=ext[j];
if ((highint-i+1)<ext[i]) ext[i]=highint-i+1;
int cst=i-ext[i];
int cdr=i+ext[i];
while (cdr<=N && cst>=1 && S[cst]==S[cdr]){
--cst;
++cdr;
}
++cst;
--cdr;
ext[i]=i-cst+1;
if (S[i]=='*') csum+=ext[i]/2; else csum+=ext[i]/2+ext[i]%2;
if (cdr>highint){
lowint=cst;
highint=cdr;
}
}
printf("%lld\n",csum);
fclose(stdout);
return 0;
}