Cod sursa(job #3206884)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 24 februarie 2024 13:20:04
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 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;
    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, k;
    for(i=0; t[i]; i++)
    {
        if(i>dr) k=1;
        else k=min(ans[dr+st-i], dr-i+1);
        while(true)
        {
            if(i-k<0 || !t[i+k]) break;
            if(t[i-k]==t[i+k]) k++;
            else break;
        }
        ans[i]=k--;
        if(dr<=i+k)
        {
            dr=i+k;
            st=i-k;
        }
    }
}