Cod sursa(job #3288569)

Utilizator Dani111Gheorghe Daniel Dani111 Data 22 martie 2025 19:57:18
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;

string s;
string t;

int main() {
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> s;
    t += "$";
    t += "#";
    for(auto i : s) {
        t += i;
        t += "#";
    }  
    t += "^"; 

    auto manacher = [](string t) {
        int ans = 0;
        int le = 1, ri = 1; //am o secventa palindromica (le + 1 ... ri - 1)
        vector<int>sz(t.size() + 1, 0); 
        //sz[i] -> cate secvente palindromice au mijlocul in i
        for(int i = 1; i < t.size(); i++) {
            sz[i] = max(0, min(sz[le + (ri - i)], ri - i));
            while(t[i - sz[i]] == t[i + sz[i]]) { sz[i]++; }

            le = min(le, i - sz[i]);
            ri = max(ri, i + sz[i]);
            ans += (sz[i]) / 2;

        }   

        cout << ans;
    };

    manacher(t);

}