Cod sursa(job #3206914)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 24 februarie 2024 13:55:48
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
const int NMAX=2000005;

using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

void manacher(int [], char*);

char s[NMAX], t[2*NMAX];
int ans[2*NMAX];

signed main()
{
    int i;
    long long sum=0;
    cin>>s;
    manacher(ans, s);
    for(i=0; t[i]; i++) sum+=(ans[i])/2+!(t[i]=='#');
    cout<<sum<<'\n';
    return 0;
}

void manacher(int v[], char *s)
{
    int i, lg=0;
    t[lg]='#';
    for(i=0; s[i]; i++)
    {
        t[++lg]=s[i];
        t[++lg]='#';
    }
    int dr=0, st=0;
    for(i=0; t[i]; i++)
    {
        if(i>dr) ans[i]=1;
        else ans[i]=min(ans[dr+st-i], dr-i+1);
        while(true)
        {
            if(i-ans[i]<0 || !t[i+ans[i]]) break;
            if(t[i-ans[i]]==t[i+ans[i]]) ans[i]++;
            else break;
        }
        ans[i]--;
        if(dr<=i+ans[i])
        {
            dr=i+ans[i];
            st=i-ans[i];
        }
    }
}