Cod sursa(job #297999)

Utilizator floringh06Florin Ghesu floringh06 Data 5 aprilie 2009 19:19:00
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "pscpld.in"
#define FOUT "pscpld.out"
#define MAX_N 1000005

char A[MAX_N];
int P[MAX_N << 1], L[MAX_N << 1], R[MAX_N << 1];
int N;

    inline int ins (int c, int d)
    {
           if (c - d >= 0 && c + d <= N) return 1;
           return 0;
    }
    
    inline int insp (int c, int d)
    {
           if (c - d >= 0 && c + d + 1 <= N) return 1;
           return 0;
    }

    void solve ()
    {
         int i, m, mp, d, c;

         P[1] = 1, m = mp = 1;
         L[1] = R[1] = 1;
                  
         for (i = 2; i < N << 1; ++i)
         {
             if (i & 1) // impar
             {
                   P[i] = 1;
                   if (m >= i) 
                   {
                         P[i] = P[(mp << 1) - i];
                         if (L[(mp << 1) - i] < L[mp] && L[(mp << 1) - i]) P[i] -= (L[mp] - L[(mp << 1) - i]) << 1;
                   }
                   
                   d = (P[i] >> 1) + 1;
                   c = (i + 1) >> 1;
                   while (A[c - d] == A[c + d] && ins(c, d)) P[i] += 2, ++d;
                   --d;
                   L[i] = c - d, R[i] = c + d;
                   if (!P[i]) L[i] = R[i] = 0;
             }
             else 
             {
                   if (m >= i) 
                   {
                         P[i] = P[(mp << 1) - i];
                         if (L[(mp << 1) - i] < L[mp] && L[(mp << 1) - i]) P[i] -= (L[mp] - L[(mp << 1) - i]) << 1;
                   }
                   
                   d = P[i] >> 1;
                   c = (i + 1) >> 1;
                   while (A[c - d] == A[c + d + 1] && insp(c, d)) P[i] += 2, ++d;
                   --d;
                   L[i] = c - d, R[i] = c + d + 1;
                   if (!P[i]) L[i] = R[i] = 0;
             }
             if ((R[i] << 1) - 1 > m) m = (R[i] << 1) - 1, mp = i;
         }
         long long BEST = 0;
         for (i = 1; i < N << 1; ++i)
         {
             if (!P[i]) continue;
             if (i & 1) BEST += P[i] / 2 + 1;
                else BEST += P[i] / 2;
         }
         printf ("%lld\n", BEST);
      //   for (i = 1; i <= N; ++i)
      //       printf ("%d ", P[i]);
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        gets (A + 1);
        N = strlen (A + 1);
        solve ();
        
        return 0;
    }