Cod sursa(job #3366939)

Utilizator livliviLivia Magureanu livlivi Data 5 octombrie 2026 11:56:45
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=2e6+5;

int manacher[nmax];
string s;

int main()
{
    string t;
    fin >> t;
    for (int i=0; i<t.size(); i++)
    {
        s+='#';
        s+=t[i];
    }
    s+='#';
    int mij = -1;
    for (int i = 0; i < s.size(); i++)
    {
        if (mij != -1 && mij + manacher[mij] - 1 >= i)
            manacher[i] = min (manacher[2 * mij - i], mij + manacher[mij] - i);
        while (i + manacher[i] < n && i - manacher[i] >= 0 && s[i + manacher[i]] == s[i - manacher[i]])
            manacher[i]++;
        if (mij == -1 || i + manacher[i] > mij + manacher[mij])
            mij = i;
    }
    long long rez=0;
    for (int i=0; i<s.size(); i++)
    {
        if (manacher[i])
            rez+=manacher[i]/2;
    }
    fout << rez;
    return 0;
}