Cod sursa(job #468138)

Utilizator vladiiIonescu Vlad vladii Data 2 iulie 2010 13:23:31
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
using namespace std;
#define maxn 1000010

int N, L[maxn];
long long sol;
char D[maxn];

void palindromimpar() {
    int i, mxx;
    L[1] = 0; mxx = 1;
    for(i=2; i<=N; i++) {
         if(i < mxx + L[mxx]) {
              L[i] = min(L[mxx - (i - mxx)], mxx + L[mxx] - i);
         }
         
         if(mxx + L[mxx] <= i + L[i]) {
              mxx = i;
              while(1 <= i - L[i] - 1 && i + L[i] + 1 <= N && D[i + L[i] + 1] == D[i - L[i] - 1]) {
                   L[i]++;
              }
         }
    }
}

void palindrompar() {
    int i, mxx;
    if(D[1] == D[2]) {
         L[1] = 1; mxx = 1;
    }
    else {
         L[1] = 0; mxx = 1;
    }
    
    for(i=2; i<=N; i++) {
         if(i < mxx + L[mxx]) {
              L[i] = min(L[mxx - (i - mxx)], mxx + L[mxx] - i);
         }
         
         if(mxx + L[mxx] <= i + L[i]) {
              mxx = i;
              while(1 <= i - (L[i] + 1) + 1 && i + L[i] + 1 <= N && D[i + L[i] + 1] == D[i - (L[i] + 1) + 1]) {
                   L[i]++;
              }
         }
    }
}

int main() {
    FILE *f1=fopen("pscpld.in", "r"), *f2=fopen("pscpld.out", "w");
    int i, j, p, q;
    fscanf(f1, "%s", D+1);
    N = strlen(D+1);
    
    palindromimpar();
    for(i=1; i<=N; i++) {
         sol += (L[i] + 1);
    }
    
    memset(L, 0, sizeof(L));
    
    palindrompar();
    for(i=1; i<=N; i++) {
         sol += L[i];
    }
    
    fprintf(f2, "%lld\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}