Pagini recente » Cod sursa (job #2144484) | Cod sursa (job #2301095) | Cod sursa (job #2683530) | Cod sursa (job #145720) | Cod sursa (job #1736324)
///v[i] - lungimea celui mai lung palindrom care incepe de pe pozitia i
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6 + 10;
int n , v[nmax] , nr;
int max_expand[nmax<<1], bst[nmax<<1], let[nmax<<1];
char s[nmax], sir[nmax<<1];
int letters(int a , int b)
{
return let[b] - let[a-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)
let[i] = (isalpha(sir[i])) ? let[i-1] + 1 : let[i-1],
bst[i] = 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]++,
bst[i+max_expand[i]] = letters(i - max_expand[i], i + 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));
for (int i = 2 * n; i >= 2 ; i -= 2)
v[++nr] = bst[i];
return 0;
}