Cod sursa(job #601555)

Utilizator floringh06Florin Ghesu floringh06 Data 6 iulie 2011 23:23:38
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define MAX_N 1000005

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

    inline bool extendable (int l1, int l2, int side) {
           if (l1 - side > 0 && l2 + side <= N && A[l1 - side] == A[l2 + side]) return 1;
           return 0;
    }

    int main () {
        freopen ("pscpld.in", "r", stdin);
        freopen ("pscpld.out", "w", stdout);
        
        gets (A + 1);
        N = strlen (A + 1);
        
        P[1] = 1;
        int m = 1, mp = 1;
        
        for (int i = 2; i <= N << 1; ++i) {
            P[i] = (i & 1) ? 1 : 0;
            
            if (i <= m) {
                  P[i] = P[2*mp - i];
                  if (L[2*mp - i] < L[mp] && L[2*mp - i]) P[i] -= 2*(L[mp] - L[2*mp - i]);
            }            
            int side = (i & 1) ? P[i]/2 : P[i] / 2 - 1;
                        
            int l1 = (i & 1) ? (i + 1)/2 : i / 2;
            int l2 = (i & 1) ? (i + 1)/2 : i / 2 + 1;
            
            ++side; while (extendable(l1, l2, side)) ++side, P[i] += 2; --side;
            
            if ((l2 + side)*2 - 1 > m) m = (l2 + side)*2 - 1, mp = i;
            L[i] = P[i] ? l1 - side : 0;
        }
        
        long long Answer = 0;
        for (int i = 1; i < N << 1; ++i) {
            if (!P[i]) continue;
            Answer += (i & 1) ? P[i]/2 + 1 : P[i]/2;
        }
        
        printf ("%lld\n", Answer);
        
        return 0;
    }