Cod sursa(job #2791250)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 30 octombrie 2021 11:49:56
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <cstring>

using namespace std;

const int NMAX = 1000000;

int n, ans[2 * NMAX + 3], centru = 1, raza;
char s[2 * NMAX + 3], inp[NMAX + 3], c;

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    scanf("%s", inp);
    s[n++] = '#';
    for(int i = 0; inp[i]; ++i) {
        s[n++] = inp[i];
        s[n++] = '#';
    }
    for(int i = 1; i < n; ++i) {
        const int simi = 2 * centru - i;
        if(i <= raza)
            ans[i] = min(raza - i, ans[simi]);
        while(i + 1 + ans[i] < n && i - 1 - ans[i] >= 0 && s[i + 1 + ans[i]] == s[i - 1 - ans[i]])
            ++ans[i];
        if(i + ans[i] > raza)
            centru = i, raza = i + ans[i];
    }
    long long anstot = 0;
    for(int i = 0; i < n; ++i)
        anstot += 1ll * ans[i] / 2 + ans[i] % 2;
    printf("%lld", anstot);
    return 0;
}