Cod sursa(job #44712)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 31 martie 2007 17:24:05
Problema PScPld Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#define NMAX 2000020

char S[NMAX], s[1000010];
long long V[NMAX];
int N;

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

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

        poz = 0; max = 1;
        V[0] = 1; i = 1;

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

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

        return 0;
        
}