Cod sursa(job #44738)

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

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

int main()
{
        int i, j, max, poz=0, num1,num2, d;
        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;

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

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

        return 0;
        
}