Pagini recente » Cod sursa (job #927171) | Cod sursa (job #1415400) | Cod sursa (job #2458351) | Cod sursa (job #1872046) | Cod sursa (job #1880714)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define NMax 1000005
#define ll long long
using namespace std;
int lps[2*NMax], N ;
char s[NMax];
void Read()
{
scanf("%s", &s);
}
void Solve()
{
int C=1, R=0, ii, N;
lps[0]=0;
lps[1]=1;
N=strlen(s);
N=2*N+1;
for(int i=2; i<=N; ++i)
{
ii=2*C-1;
int dif=R-i;
lps[i]=0;
if(dif>0)
lps[i]=min(dif,lps[ii]);
while ( ((i + lps[i]) < N && (i - lps[i]) > 0) &&
( ((i + lps[i] + 1) % 2 == 0) ||
(s[(i + lps[i] + 1)/2] == s[(i - lps[i] - 1)/2] )))
lps[i]++;
if(i+lps[i] > R)
{
C=i;
R=i+lps[i];
}
}
}
void Print()
{
ll Sum=0;
for(int i=1; i<=N-1; ++i)
{
if(lps[i]%2==0)
Sum+=lps[i]/2;
else
Sum+=lps[i]/2+1;
}
printf("%lld", Sum);
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
Read();
Solve();
Print();
return 0;
}