Cod sursa(job #1736324)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 1 august 2016 16:04:13
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
///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;
}