Pagini recente » Cod sursa (job #491318) | Cod sursa (job #1982376) | Cod sursa (job #855876) | Cod sursa (job #2067069) | Cod sursa (job #644979)
Cod sursa(job #644979)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Nmax 1000002
using namespace std;
char v[Nmax];
int l[2*Nmax];
long long sol;
int main(){
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
fgets(v,Nmax,stdin);
int N=strlen(v)-1;
for(int i=0;i<=2*N;++i){
int d=(l[i]/2);
bool ok=0;
while( i+d+1<2*(N+1) && d < i-l[i] && i/2+d+1<=N && i/2-d-1 + i%2>=0 && v[i/2+d+1]==v[i/2-d-1 + i%2] ){
++d;
ok=1;
}
for(int j=d;j>l[i]/2;--j){
l[i+2*j]=min(l[i-2*j],2*(d-j)+1);
l[i+2*j-1]=min(l[i-2*j+1],2*(d-j+1));
}
if(ok || l[i]==0)
l[i]=2*d+(1-i%2);
sol+=l[i]/2+1-i%2;
}
printf("%lld",sol);
return 0;
}