Cod sursa(job #1444324)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 29 mai 2015 16:04:56
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
/*
    If you can't explain it simply, you don't understand it well enough.
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int Nmax = 100010;

int n , i , lg , sol , right , C;
int max_expand[2*Nmax];

char aux[Nmax] , sir[2*Nmax];

int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);

    gets(aux + 1); n = strlen(aux + 1);

    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 += (max_expand[i] + 1) >> 1;

        if (i + max_expand[i] > right)
            C = i, right = i + max_expand[i];
    }

    printf("%d\n", sol);

    return 0;
}