Cod sursa(job #2175136)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 16 martie 2018 15:32:57
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = (int) 1e6 + 5;

char str[MAXN + 1];
char aux[2 * MAXN + 1];

int len[2 * MAXN + 1];

int main() {
    FILE *fi, *fout;
    int i, n;
    fi = fopen("pscpld.in" ,"r");
    fout = fopen("pscpld.out" ,"w");
    fgets(str + 1, MAXN, fi);
    int sz = strlen(str + 1) - 1;
    n = 0;
    aux[++n] = '*';
    for(i = 1; i <= sz; i++) {
        aux[++n] = str[i];
        aux[++n] = '*';
    }
    int pos = 0;
    for(i = 1; i <= n; i++) {
        if(pos + len[pos] >= i) {
            len[i] = min(pos + len[pos] - i, len[2 * pos - i]);
        }
        while(i - len[i] > 0 && i + len[i] <= n && aux[i - len[i]] == aux[i + len[i]])
            len[i]++;
        if(i + len[i] > pos + len[pos])
            pos = i;
    }
    long long ans = 0;
    for(i = 1; i <= n; i++) {
        ans += len[i] / 2;
    }
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}