Cod sursa(job #2791244)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 30 octombrie 2021 11:47:21
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 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], c;

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    s[n++] = '#';
    while(scanf("%c", &c) != -1) {
        if(!isalpha(c)) break;
        s[n++] = c;
        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];
    }
    int anstot = 0;
    for(int i = 0; i < n; ++i)
        anstot += ans[i] / 2 + ans[i] % 2;
    printf("%d", anstot);
    return 0;
}