Cod sursa(job #3304101)

Utilizator aaagabiTurbinca Gabriel aaagabi Data 20 iulie 2025 17:29:09
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
#define int long long

int manacher(const string &t)
{
    string s = "";
    for(char ch : t)
    {
        s += ch;
        s += '*';
    }
    //cout<<s;
    //cout<<'\n';
    vector<int> aux(s.size(), 0);
    int centru = 0, dr = 1, ans = 0;
    for(int i = 0; i < s.size(); i++)
    {
        int st = 2 * centru - i;
        if(i < dr)
            aux[i] = min(dr - i, aux[st]);
        while(i + aux[i]  < s.size() && i - aux[i]  >= 0 && s[i + aux[i]] == s[i - aux[i]])
            aux[i]++;
        if(i + aux[i] > dr)
        {
            dr = i + aux[i];
            centru = i;
        }
        ans += aux[i]/2+(s[i+aux[i]-1]!='*'&&s[i]!='*');
        //cout<<i<<' '<<aux[i]<<' '<<ans<<'\n';
    }
    return ans;
}

signed main()
{
    string s;
    fin >> s;
    fout << manacher(s);

    fin.close();
    fout.close();
    return 0;
}