Pagini recente » Cod sursa (job #414988) | Cod sursa (job #1235536) | Cod sursa (job #2359648) | Cod sursa (job #715547) | Cod sursa (job #1212755)
#include <cstdio>
#include <cstring>
#define Nmax 2000005
using namespace std;
char a[Nmax],b[Nmax];
int N,Z[Nmax];
long long sol;
inline void Manacher()
{
int L,M=0,R=0,t,i;
Z[1]=0;
for(i=2;i<=N;++i)
if(i>R)
{
M=i;
for(R=M+1;R<=N && a[R]==a[2*M-R];++R);
--R;
Z[i]=R-M;
}
else
{
t=2*M-i; L=2*M-R;
if(Z[t]<t-L)
Z[i]=Z[t];
else
{
M=i;
for(++R;R<=N && a[R]==a[2*i-R];++R);
--R;
Z[i]=R-M;
}
}
}
int main()
{
int i;
freopen ("pscpld.in","r",stdin);
freopen ("pscpld.out","w",stdout);
scanf("%s", (a+1));
N=strlen(a+1);
Manacher();
for(i=1;i<=N;++i)
sol+=Z[i];
sol+=N;
for(i=1;i<=N;++i)
{
b[2*i]=a[i]; b[2*i-1]='*';
}
b[2*N+1]='*';
N=2*N+1;
for(i=1;i<=N;++i)
a[i]=b[i];
Manacher();
for(i=3;i<=N;i+=2)
sol+=(Z[i]/2);
printf("%lld\n", sol);
return 0;
}