Pagini recente » Cod sursa (job #1783217) | Cod sursa (job #847625) | Cod sursa (job #3158747) | Cod sursa (job #507942) | Cod sursa (job #1527482)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define in "pscpld.in"
#define out "pscpld.out"
#define NMAX 2000007
#define LL long long
using namespace std;
int sol[NMAX], n, mij, edge;
char s[NMAX];
LL rez;
inline void convert()
{
n=strlen(s+1);
for(int i=n;i;i--)
{
s[(i<<1)] = s[i];
s[(i<<1)-1] = '$';
}
n = (n<<1)|1;
s[n] = '$';
mij = edge = 1;
}
inline void manacher()
{
for(int i=2; i<=n; ++i)
{
if(i <= edge) sol[i] = min(sol[(mij<<1) - i], edge - i);
while(1 <= i-sol[i]-1 && i+sol[i]+1 <= n && s[i-sol[i]-1] == s[i+sol[i]+1]) sol[i]++;
if(i+sol[i] > edge)
{
edge=i+sol[i];
mij=i;
}
}
}
inline void afisare()
{
for(int i=1; i<= n; ++i)
if(i&1) rez += ((sol[i]+1)>>1);
else rez += ((sol[i]+2)>>1);
printf("%lld",rez);
}
int main()
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
scanf("%s",s+1);
convert();
manacher();
afisare();
return 0;
}