Cod sursa(job #1391349)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 17 martie 2015 21:08:39
Problema PScPld Scor 100
Compilator cpp Status done
Runda oni2015.1112.bv.1 Marime 1.06 kb
#include <cstdio>
#include <cstring>

#define Nmax 1000100
#define Smax 2000100

using namespace std;
char c[Nmax],A[Smax];
int N,DP[Smax];

int mini(int a,int b){
    if(a < b) return a;
    return b;
}

void Read()
{
    scanf("%s",c);
    int lg = strlen(c);
    A[0] = '$';A[1] = '#'; N = 1;
    for(int i = 0; i < lg; ++i){
        A[++N] = c[i];
        A[++N] = '#';
    }
    A[N+1] = 0;
}

void Manacher()
{
    int right,center,_i;
    right = center = 0;
    long long rez = 0;
    for(int i = 1; i <= N; ++i)
    {
        _i = (center<<1) - i; /// simetricul fata de centru
        if(i <= right)
            DP[i] = mini(DP[_i], right - i);
        while(A[i - DP[i] - 1] == A[i + DP[i] + 1])
            ++DP[i];
        if(i + DP[i] > right){
            right = i + DP[i];
            center = i;
        }
        rez +=  (DP[i] + 1) >> 1;
    }
    printf("%lld\n",rez);
}

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

    Read();
    Manacher();

    return 0;
}