Cod sursa(job #2412191)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 21 aprilie 2019 19:30:41
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
#define MAXN 1000000

int n;
char S[1 + MAXN];
int LPS[2 * MAXN];

void Manacher(char S[], int n, int LPS[]){
    char T[2 * MAXN];
    for(int i = 1; i < n; i++){
        T[2 * i - 1] = S[i];
        T[2 * i] = '*';
    }
    T[2 * n - 1] = S[n];
    n = 2 * n - 1;

    int p = 1;
    for(int i = 1; i <= n; i++){
        LPS[i] = std::max(0, std::min(p + LPS[p] - i, LPS[2 * p - i]));
        while(i - (LPS[i] + 1) >= 1 && i + (LPS[i] + 1) <= n &&
              T[i - (LPS[i] + 1)] == T[i + (LPS[i] + 1)]) LPS[i]++;
        if(i + LPS[i] > p + LPS[p])
            p = i;
    }
}

int main(){
    FILE*fi,*fo;
    fi = fopen("pscpld.in","r");
    fo = fopen("pscpld.out","w");

    char c = fgetc(fi);
    while('a' <= c && c <= 'z'){
        S[++n] = c;
        c = fgetc(fi);
    }
    Manacher(S, n, LPS);

    long long ans = 0;
    for(int i = 1; i < 2 * n; i++)
        if(i % 2 == 1) ans += (LPS[i]) / 2 + 1;
        else ans += (LPS[i] + 1) / 2;
    fprintf(fo,"%lld", ans);

    return 0;
}