Cod sursa(job #3305881)

Utilizator Tudor_11Tudor Ioan Calin Tudor_11 Data 5 august 2025 21:10:03
Problema PScPld Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int manacher[1000001];
int main()
{
    string a,s;
    fin>>a;
    s="##";
    for(int i=0;i<a.size();i++)
    {
        s+=a[i];
        s+='#';
    }
    int best=0;
    for(int i=1;i<s.size();i++)
    {
        if(best+manacher[best]>=i)
        {
            manacher[i]=min(manacher[best-(i-best)],best+manacher[best]-i);
            while(i+manacher[i]+1<s.size() && i-manacher[i]-1>=1 && s[i+manacher[i]+1]==s[i-manacher[i]-1])
            {
                manacher[i]++;
            }
            if(i+manacher[i]>=best+manacher[best])
            {
                best=i;
            }
        }
        else
        {
            manacher[i]=0;
            while(i+manacher[i]+1<s.size() && i-manacher[i]-1>=1 && s[i+manacher[i]+1]==s[i-manacher[i]-1])
            {
                manacher[i]++;
            }
            best=i;
        }
    }
    long long ans=0;
    for(int i=1;i<s.size();i++)
    {
        ans+=(manacher[i]+1)/2;
    }
    fout<<ans;
    return 0;
}