Cod sursa(job #3292849)

Utilizator parrot279Sofi Tudose parrot279 Data 9 aprilie 2025 14:38:06
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

string s, sir;
int manacher[2000001], best = 0, n, nrpal = 0;

int main()
{
    cin>>s;
    n = s.size();
    sir = "%$";
    for(int i = 0; i < n; ++i)
    {
        sir += s[i];
        sir += "$";
    }
    sir += "#";
    n = sir.size();

    for(int i = 1; i < n - 1; ++i)
    {
        int capatdr = best + manacher[best];
        int j = 2 * best - i;
        if(i < capatdr)
        {
            manacher[i] = min(capatdr - i, manacher[j]);
        }
        else
        {
            manacher[i] = 0;
        }
        while(i + manacher[i] < n - 1 && sir[i + manacher[i] + 1] == sir[i - manacher[i] - 1])
        {
            ++manacher[i];
        }

        if(i + manacher[i] > capatdr)
            best = i;

        nrpal += (manacher[i] + 1) / 2;

    }
    cout<<nrpal<<"\n";
    return 0;
}