Pagini recente » Cod sursa (job #2042541) | Cod sursa (job #2350424) | Cod sursa (job #1729595) | Cod sursa (job #2894574) | Cod sursa (job #1304671)
#include <cstdio>
#include <cstring>
FILE* in=fopen("pscpld.in","r");
FILE* out=fopen("pscpld.out","w");
const int Q=1000007;
char v[2*Q],h[Q];
int p[2*Q];
int min(const int &a, const int &b)
{
return a<b?a:b;
}
int n;
int main()
{
fgets(h+1,Q,in);
n=strlen(h+1);
if(h[n]=='\n')
n--;
v[0]='#';
int aux=0;
for(int i=1; i<=n; i++)
{
v[++aux]=',';
v[++aux]=h[i];
}
v[++aux]=',';
v[++aux]='$';
int max_right=0,max_center=0;
long long rez=0;
int d;
for(int i=1; i<=2*n+1; i++)
{
d=0;
if(i<max_right)
{
d=min(max_right-i,p[2*max_center-i]);
}
while(v[i-d-1]==v[i+d+1])
d++;
p[i]=d;
rez+=(long long)(p[i]+1)/2;
if(i+d>max_right)
{
max_right=i+d;
max_center=i;
}
}
fprintf(out,"%ld",rez);
return 0;
}