Cod sursa(job #46807)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 2 aprilie 2007 23:24:15
Problema PScPld Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <stdio.h>
#define NMAX 2000020

char S[NMAX], s[1000010];
int V[NMAX], V2[NMAX], V3[NMAX], Ramas[NMAX];
int N;

int main()
{
        int i, j, max, poz=0, num, d, it = 0;
        long long sum=0;

        freopen("pscpld.in", "r", stdin);
        gets(s);
        N = strlen(s);
        S[poz++] = ' ';
        for (i = 0; i < N; i++)
            S[poz++] = s[i], S[poz++] = ' ';
        N = poz-1;

        poz = 1; max = 1;
        V[1] = 1; i = 1; V2[i] = 1; V3[i] = 1;
        Ramas[N-1] = 1;

        for (j = N-2; j >= 0; j--) Ramas[j] = Ramas[j+1]+(S[j]!=' ');

        for (i = 2; i <= N; i++)
        {
                j = num = 0;
                d = i-poz;
                if (i-poz+1 <= max) j = V2[poz-d], num = V3[poz-d];
                if (j>=N) j = Ramas[i];
                while ((i-j>=0)&&(i+j<N)&&(S[i-j] == S[i+j]))
                        V2[i]++, num += (S[i-j] != ' '), j++;
                V3[i] = num; V[i] = (num<<1)-(S[i]!=' ');
                if ((V[i]>max) || (V[i]==max && poz<i)) max = V[i], poz = i;
        }

        for (i = 1; i <= N; i++) sum+=((V[i]>>1)+(V[i]&1));
        freopen("pscpld.out", "w", stdout);
        printf("%lld\n", sum);

        return 0;
        
}