Cod sursa(job #46863)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 3 aprilie 2007 09:38:30
Problema PScPld Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#define NMAX 2000020
#define MIN(a,b) ((a)<(b)?(a):(b))
#define BIGINT long long //__int64
#define format "%lld\n" // "%I64d\n"

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

int main()
{
        int i, j, max, poz=0, num1,num2, d, it = 0;
        BIGINT 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;
        for (i=1; i <= N; i++) V[i] = 1; 
		V[1] = 3;
		i = 1;

		//freopen("pscpld.out", "w", stdout);
        for (i = 2; i < N; i++)
        {
			j = (V[i]+1)>>1;
			while ((S[i-j]==S[i+j]) &&(i-j>=0 && i+j <= N))
			{
					if (!(j&1)) V[((i<<1)+j)>>1] = MIN(j+1,V[((i<<1)-j)>>1]);
					V[i]+=2; j++;
			}
		//	printf("%d %c\n", V[i], S[i]);
        }

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

        return 0;
        
}