Cod sursa(job #1303280)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 decembrie 2014 20:17:24
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

#define Nmax 2000005

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

void read()
{
    fgets(c+1,Nmax-1,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()
{
    int center,right,_i;
    center = right = 0;
    for(int i = 1; i < N; ++i)
    {
        _i = 2*center - i;
        if(right > i)
            DP[i] = min(DP[_i],right - i);
        while(a[i - DP[i] - 1] == a[i + DP[i] + 1])
            ++DP[i];
        if( i + DP[i] > right){
            center = i;
            right = i + DP[i];
        }
        ans += (DP[i] + 1) / 2;
    }
    printf("%lld\n",ans);
}

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

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

    return 0;
}