Pagini recente » Mere | Cod sursa (job #2300624) | Cod sursa (job #2332082) | Cod sursa (job #3252131) | Cod sursa (job #1880265)
#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) && ((s[(i-LPS[i]-1)/2] == s[(i + LPS[i]+1)/2]) || ((1+LPS[i]+i)%2 == 0 )))
LPS[i]++;
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;
}