Pagini recente » Monitorul de evaluare | Atasamentele paginii Profil drayne | Istoria paginii utilizator/mihai-vijulie | Profil HGbyte | Cod sursa (job #2336700)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
char a[1000010];
char s[2000010];
int p[2000010];
int n;
void addHash(){
n=strlen(a);
for(int i=0; i<n; i++)
{
s[2*i]='#';
s[2*i+1]=a[i];
}
s[2*n]='#';
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
scanf("%s",a);
addHash();
int simi, C=0, R=0;
int m=2*n;
long long vmax=0;
for(int i=0; i<=m; i++)
{
simi=C-(i-C);
if(i<=R)
p[i]=min(p[simi],R-i);
while(s[i+1+p[i]]==s[i-1-p[i]] && i+1+p[i]<=m && i-1-p[i]>=0)
p[i]++;
if(i+p[i]>=R)
{
C=i;
R=i+p[i];
}
vmax=vmax+1LL*(p[i]+1)/2;
}
printf("%lld",vmax);
return 0;
}