Cod sursa(job #1960289)

Utilizator mihai.alphamihai craciun mihai.alpha Data 10 aprilie 2017 12:38:51
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

const int dim = 1000000;

FILE *fin = fopen("pscpld.in", "r");
FILE *fout = fopen("pscpld.out", "w");

char *s = new char[dim + 2], a[dim * 2 + 4];
int l[dim * 2 + 4];

int main()  {
    fgets(s + 1, dim + 2, fin);
    int n = strlen(s + 1) - 1;
    for(int i = 1;i <= n;i++)
        a[2 * i - 1] = '*', a[2 * i] = s[i];
    a[2 * n + 1] = '*';
    int m = 2 * n + 1;
    int id = 0;
    long long ans = 0LL;
    for(int i = 1;i <= m;i++)  {
        if(id + l[id] > i) l[i] = min(l[2 * id - i], id + l[id] - i);
        else  l[i] = 1;
        while(i > l[i] && a[i - l[i]] == a[i + l[i]]) ++l[i];
        ans += 1LL * (l[i] / 2);
        if(i + l[i] > id + l[id])
            id = i;
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}