Cod sursa(job #2537403)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 3 februarie 2020 17:20:02
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("pscpld.in");
ofstream fo("pscpld.out");

using i64 = long long;

const int N = 2e6 + 5;

char str[N], _str[N];
int man[N];

int n, m;
i64 ant;

int main() {
    fi >> (_str + 1);

    n = strlen(_str + 1);
    m = 2 * n + 3;

    str[0] = '$';
    for (int i = 1; i <= n; ++i) {
        str[2 * i - 1] = '*';
        str[2 * i] = _str[i];
    }
    str[2 * n + 1] = '*';
    str[2 * n + 2] = '#';

    for (int p = 1, i = 1; i <= m; ++i) {
        if (i >= p + man[p]) {
            p = i;
            while (str[p - man[p]] == str[p + man[p]])
                man[p]+= 1;
            ant+= man[i] / 2;
            continue;
        }

        man[i] = min(p + man[p] - i, man[2 * p - i]);
        while (str[i - man[i]] == str[i + man[i]])
            man[i]+= 1;
        
        ant+= man[i] / 2;
    }

    fo << ant << endl;

    return 0;
}