Cod sursa(job #3186884)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 26 decembrie 2023 12:10:22
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<fstream>
std::ifstream fin("pscpld.in");
std::ofstream fout("pscpld.out");
std::string s;
int vec[2500000];
long long size;
void precalc()
{
    fin>>s;
    size=s.size();
    for(int index=0; index<size; ++index)
    {
        s.insert(s.begin()+index,'#');
        ++size;
        ++index;
    }
    s.insert(s.end(), '#');
    ++size;
}
void manacher()
{
    int c=0, r=0;
    for(int index=0; index<size; ++index)
    {
        int sim=2*c-index;
        vec[index]=std::max(0, std::min(vec[sim], r-index));
        while(s[index+vec[index]]==s[index-vec[index]] && index+vec[index]<size && index-vec[index]>=0)
            ++vec[index];
        if(index+vec[index]>r)
        {
            r=index+vec[index];
            c=index;
        }
    }
}
bool isLetter(char x)
{
    return x>='a' && x<='z';
}
void getTotal()
{
    int ans=0;
    for(int index=0; index<size; ++index)
    {
        if(isLetter(s[index]))
            while(vec[index]>0)
            {
                ++ans;
                vec[index]-=2;
            }
        else
            while(vec[index]>1)
            {
                ++ans;
                vec[index]-=2;
            }
    }
    fout<<ans;
}
int main()
{
    precalc();
    manacher();
    getTotal();
    return 0;
}