Cod sursa(job #1787771)

Utilizator silkMarin Dragos silk Data 24 octombrie 2016 23:42:55
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#include <cstring>
#define NMax 2000005
#define MIN(a,b)((a)<(b)?(a):(b))

char s[NMax+1];
char v[NMax+1];
int best[NMax+1];
int N,t;

void Update()
{
    int i,t;

    for(t = 1, i = 0; i < N; ++i)
    {
        v[t++] = s[i];
        v[t++] = '#';
    }
    v[0] = '#';
    v[--t] = '#';
    N = --t;
}

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

    int R,C,i,ii,j;
    long long ans = 0;

    fgets(s, NMax-1, stdin);
    N = strlen(s);
    if(s[N-1]=='\n') --N;

    Update();
    R = C = 0;

    for(i = 1; i <= N; ++i)
    {
        ii = 2*C-i;
        best[i] = ( R>i? MIN( best[ii], R-i ) : 0 );

        j = best[i];
        while( v[i+j] == v[i-j] && (i+j<=N+1) && (i>=j) ) ++j;
        --j;

        best[i] = j;
        if( i + j > C + R )
        {
            R = j;
            C = i;
        }
    }

    for(i = 1; i <= N; ++i)
    if( v[i] == '#' ) ans = ans + best[i]/2;
    else ans = ans + best[i]/2 + 1;

    printf("%lld\n",ans);



return 0;
}