Cod sursa(job #3363877)

Utilizator robertcosacCosac Robert-Mihai robertcosac Data 24 august 2026 17:34:30
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char s[2000009];
char copie[1000009];
int n;
int l[2000009];
void manacher ()
{
    s[1]='*';
    for (int i=1; i<=n; i++)
        s[2*i]=copie[i], s[2*i+1]='*';
    int poz=0;
    //cout << (s+1);
    n=2*n+1;
    for (int i=1; i<=n; i++)
    {
        if (poz+l[poz]<i)
        {
            poz=i;
            int st=i-1, dr=i+1;
            while (st>=1 && dr<=n && s[st]==s[dr])
            {
                st--;
                dr++;
                l[poz]++;
            }
        }
        else
        {
            int ogl=2*poz-i;
            if (poz+l[poz]>i+l[ogl])
                l[i]=l[ogl];
            else if (poz+l[poz]<i+l[ogl])
                l[i]=poz+l[poz]-i;
            else if (poz+l[poz]==i+l[ogl])
            {
                l[i]=l[ogl];
                int st=i-l[i]-1, dr=i+l[i]+1;
                bool ok=0;
                while (st>=1 && dr<=n && s[st]==s[dr])
                {
                    ok=1;
                    l[i]++;
                    st--;
                    dr++;
                }
                if (ok) poz=i;
            }
        }
    }
}
signed main ()
{
    f.getline (copie+1, 1000001);
    n=strlen (copie+1);
    manacher ();
    int ans=0;
    for (int i=1; i<=n; i++)
    {
        if (s[i]=='*')
        {
            ans+=l[i]/2;
            //cout << l[i]/2<<'\n';
        }
        else
        {
            ans+=l[i]/2+1;
            //cout << l[i]/2+1 <<'\n';
        }
    }
    g << ans;
}