Cod sursa(job #2548162)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 16 februarie 2020 12:34:05
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 sol = 0;
    for (int i = 0; i < n; i++)
        sol += d1[i] + d2[i];
    fout << sol << '\n';

    fout.close();
    return 0;
}