Cod sursa(job #297408)

Utilizator floringh06Florin Ghesu floringh06 Data 5 aprilie 2009 13:17:02
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <cstdio>
#include <cstring>

using namespace std;

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

char A[MAX_N];
long long P[MAX_N << 1];
int N;

    inline int ok (int c1, int c2, int let)
    {
           if (c1 - let > 0 && c2 + let <= N) return 1;
           return 0;
    }

    void solve ()
    {
         int i, c, mex, mirr, mex_i, let, c1, c2, dif;
         
         // initializari
         P[1] = 1;
         mex = 1, mex_i = 1;
         
         for (i = 2; i <= N << 1; ++i)
         if (i & 1)
         {
                   P[i] = 1;
                   dif = i - mex_i;
                   if (i <= mex)
                      mirr = mex_i - dif;
                   else 
                      mirr = i;  
                      
                   P[i] = P[mirr], let = P[mirr] / 2;
                   
                   c1 = c2 = (i + 1) >> 1;
                   
                   ++let;   
                   while (A[c1 - let] == A[c2 + let] && ok (c1, c2, let)) ++let, P[i] += 2;
                   --let;
                   
                   int nm = ((c2 + let) << 1) - 1;
                   if (nm > mex) mex = nm, mex_i = i;
         }
         else 
         {
                   dif = i - mex_i;
                   if (i <= mex)
                      mirr = mex_i - dif;
                   else 
                      mirr = i;  
                      
                   P[i] = P[mirr], let = P[mirr] / 2 - 1;
                   
                   c1 = i >> 1, c2 = c1 + 1;
                   ++let;   
                   while (A[c1 - let] == A[c2 + let] && ok (c1, c2, let)) ++let, P[i] += 2;
                   --let;
                   
                   int nm = ((c2 + let) << 1) - 1;
                   if (nm > mex) mex = nm, mex_i = i;
         }
         long long BEST = 0;
         for (i = 1; i <= N << 1; ++i)
         {
             if (!P[i]) continue;
             if (i & 1) BEST += (long long)(P[i]/2 + 1);
                else BEST += (long long)P[i]/2;
         }
         printf ("%lld\n",(long long) BEST);
    }

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