Pagini recente » Borderou de evaluare (job #1599923) | Cod sursa (job #104425) | Cod sursa (job #1601070) | Cod sursa (job #871450) | Cod sursa (job #1880299)
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMax 1000005
using namespace std;
char s[NMax];
int LPS[2*NMax+2], N;
void Read()
{
scanf("%s", &s);
N=strlen(s);
}
void Solve()
{
int C,R;
int expand, lmax, cmax,ii,ok;
LPS[0]=0;
LPS[1]=1;
C=1;
R=2;
N=2*N+1;
for(int i=2; i<=N; ++i)
{
int ii=2*C-1;
if(i<R)
{
if(LPS[ii]<R-i)
LPS[i]=LPS[ii];
else
LPS[i]=R-i;
}
else
LPS[i]=0;
while(i - LPS[i]-1 >= 0 && i + LPS[i] + 1 <= N)
{if((1+LPS[i]+i)%2 == 0)
LPS[i]++;
else
if(s[(i-LPS[i]-1)/2]==s[(i+LPS[i]+1)/2])
LPS[i]++;
else
break;
}
if(i+LPS[i]>R)
{
R=i+LPS[i];
C=i;
}
}
long long S=0;
for(int i=1; i< N-1; ++i)
{
if(LPS[i]%2==0)
S+=LPS[i]/2;
else
S+=LPS[i]/2+1;
}
printf("%lld", S);
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
Read();
Solve();
return 0;
}