Cod sursa(job #1303244)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 decembrie 2014 19:40:46
Problema PScPld Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

#define Nmax 1000005

using namespace std;
char c[Nmax*2],a[Nmax*2];
int DP[Nmax*2];
int nr,N;
long long ans;

void read()
{
    fgets(c+1,Nmax,stdin);
    c[0]='#';
    if(c[strlen(c)-1] == '\n')
        c[strlen(c)-1] = 0;
    nr = strlen(c+1);
}

void expand()
{
    a[N++] = '&';
    a[N] = '#';
    for(int i = 1 ; i <= nr; ++i)
    {
        a[++N] = c[i];
        a[++N] = '#';
    }
    a[++N] = '$';
}

void manacher()
{
    DP[1] = 1;
    int center,right,_i;
    center = right = 0;
    for(int i = 1; i < N; ++i)
    {
        _i = 2*center - i;
        if(_i >= 1)
            DP[i] = (i < right) ? min(DP[_i],right - i) : 1;
        else
            DP[i] = (i < right) ? right - i : 1;
        while(a[i - DP[i]] == a[i + DP[i]])
            ++DP[i];
        if(center + DP[i] > right){
            right = center + DP[i];
            center = i;
        }
        ans += DP[i] / 2;
    }
    printf("%lld\n",ans);
}

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

    read();
    expand();
    manacher();

    return 0;
}