Cod sursa(job #2574249)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 5 martie 2020 21:08:01
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda OJI 2020 Partea a II-a Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

int main() {
    string str; fin >> str;
    int n = str.size();

    vector<int> d1(n);
    for (int i = 0, l = 0, r = 0; i < n; i++) {
        int x = i, y = i;
        if (r >= i) {
            x = max(l, i - d1[l + r - i] / 2);
            y = min(r, i + d1[l + r - i] / 2);
        }
        for (; 0 <= x - 1 && y + 1 < n && str[x - 1] == str[y + 1]; x--, y++);
        d1[i] = y - x + 1;
        if (y > r) {
            l = x;
            r = y;
        }
    }

    vector<int> d2(n);
    for (int i = 1, l = 1, r = 0; i < n; i++) {
        int x = i, y = i - 1;
        if (r >= i) {
            x = max(l, i - d2[l + r - i] / 2);
            y = min(r, i + d2[l + r - i] / 2 - 1);
        }
        for (; 0 <= x - 1 && y + 1 < n && str[x - 1] == str[y + 1]; x--, y++);
        d2[i] = y - x + 1;
        if (y > r) {
            l = x;
            r = y;
        }
    }

    int64_t cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += d1[i] / 2 + d2[i] / 2 + 1;
    fout << cnt << '\n';

    fout.close();
    return 0;
}