Cod sursa(job #3299093)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 4 iunie 2025 15:46:01
Problema PScPld Scor 100
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]<s.size() && 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;
}