Cod sursa(job #3359518)

Utilizator rares89_Dumitriu Rares rares89_ Data 29 iunie 2026 13:29:03
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

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

string s;
vector<int> d1, d2;
long long ans;

int main() {
    fin >> s;

    int n = s.size();

    d1.resize(n);
    d2.resize(n);

    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = 1;

        if (i <= r)
            k = min(d1[l + r - i], r - i + 1);

        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
            ++k;

        d1[i] = k;

        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
    }

    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = 0;

        if (i <= r)
            k = min(d2[l + r - i + 1], r - i + 1);

        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k])
            ++k;

        d2[i] = k;

        if (i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
    }

    for (int i = 0; i < n; ++i)
        ans += d1[i] + d2[i];

    fout << ans << "\n";

    return 0;
}