Cod sursa(job #2574374)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 5 martie 2020 21:52:48
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 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 = -1; i < n; i++) {
        int k = (i > r ? 1 : min(d1[l + r - i], r - i + 1));
        while (0 <= i - k && i + k < n && str[i - k] == str[i + k])
            k++;
        d1[i] = k--;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }

    vector<int> d2(n);
    for (int i = 0, l = 0, r = -1; i < n; i++) {
        int k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1));
        while (0 <= i - k - 1 && i + k < n && str[i - k - 1] == str[i + k])
            k++;
        d2[i] = k--;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }

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

    fout.close();
    return 0;
}