Cod sursa(job #2768475)

Utilizator DragosC1Dragos DragosC1 Data 10 august 2021 22:58:32
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
using namespace std;

int p[2000005];
string s, aux;

void read() {
    int i;
    ifstream f("pscpld.in");
    s = '#';
    f >> aux;
    for (i = 0; i < aux.size(); i++) {
        s += aux[i];
        s += '#';
    }
    f.close();
}

long long nr;

void solve() {
    int i, C, R, i_mirror;
    C = 0, R = 0;
    for (i = 1; i < s.size(); i++) {
        i_mirror = C - (i - C);
        if (R > i)
            p[i] = min(R - i, p[i_mirror]);
        else p[i] = 0;

        while (i + 1 + p[i] < s.size() && i - 1 - p[i] >= 0 && s[i + 1 + p[i]] == s[i - 1 - p[i]])
            p[i]++;

        if (i + p[i] > R) {
            C = i;
            R = i + p[i];
        }
        nr += (p[i] + 1) / 2;
    }
}

void output() {
    ofstream g("pscpld.out");
    g << nr;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}