Pagini recente » Cod sursa (job #550272) | Cod sursa (job #2954178) | Cod sursa (job #1004525) | Cod sursa (job #132350) | Cod sursa (job #1880256)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMax 1000010
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;
lmax=1;
cmax=1;
for(int i=2; i<=N; ++i)
{
int ii=2*C-1;
if(i<R)
{
if(R-i<LPS[ii])
LPS[i]=R-i;
else
LPS[i]=LPS[ii];
}
else
LPS[i]=0;
while((i-LPS[i]-1)>=0 &&(i+LPS[i]+1)<=N)
{
if((i-LPS[i]-1)%2==0)
LPS[i]++;
else
{if(s[i-LPS[i]-1]==s[i+LPS[i]+1])
LPS[i]++;
else
break;
}
}
if(lmax<LPS[i])
{
lmax=LPS[i];
cmax=i;
}
if(i+LPS[i]>R)
{
R=i+LPS[i];
C=i;
}
}
long long S=0;
for(int i=1; i<=N-2; ++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;
}