Pagini recente » Cod sursa (job #91545) | Cod sursa (job #1675570) | Cod sursa (job #1736329)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6 + 10;
int n;
int max_expand[nmax<<1], let[nmax<<1];
char s[nmax], sir[nmax<<1];
long long manacher(char aux[nmax])
{
long long sol = 0;
int i , lg(0), right(0), C(0);
sir[lg] = '$'; sir[++lg] = '#';
for (i = 1; i <= n; ++i)
{
sir[++lg] = aux[i];
sir[++lg] = '#';
}
sir[lg+1] = '*';
for (i = 1; i <= lg; ++i)
{
int simetric_C = C - (i - C);
max_expand[i] = (right > i) ? min(max_expand[simetric_C] , right - i) : 0;
while (sir[i+max_expand[i]+1] == sir[i-max_expand[i]-1])
max_expand[i]++;
sol += 1LL * (max_expand[i] + 1) >> 1;
if (i + max_expand[i] > right)
C = i, right = i + max_expand[i];
}
return sol;
}
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
gets(s + 1); n = strlen(s + 1);
reverse(s + 1 , s + n + 1);
printf("%lld\n", manacher(s));
return 0;
}