Cod sursa(job #3304099)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 20 iulie 2025 17:03:38
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

int manacher(const string &t)
{
    string s = "";
    for(char ch : t)
    {
        s += ch;
        s += '*';
    }
    vector<int> aux(s.size(), 0);
    int centru = 0, dr = 0, 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] + 1 < s.size() && i - aux[i] - 1 >= 0 && s[i + aux[i] + 1] == s[i - aux[i] - 1])
            aux[i]++;
        if(i + aux[i] > dr)
        {
            dr = i + aux[i];
            centru = i;
        }
        ans += (s[i] == '*' ? (aux[i] / 2) : (aux[i] / 2 + 1));
    }
    return ans;
}

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

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