Cod sursa(job #2701904)

Utilizator HardtoPronouncePetcu David-Andrei HardtoPronounce Data 2 februarie 2021 09:45:13
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

const int dim1=1e6+5;
const int dim2=2e6+5;
int n;
char t[dim2], v[dim1];
int l[dim2];

void extraprep()
{
    int len=strlen(v);
    for (int i=len;i>=1;i--)
        v[i]=v[i-1];
}

void prep()
{
    f>>v;
    extraprep();
    int len=strlen(v+1);
    for (int i=1;i<=len;i++){
        t[2*i-1]='#';
        t[2*i]=v[i];
    }
    t[2*len+1]='#';
    n=2*len+1;
}

long long manach()
{
    long long rez=0;
    int r=0,c=0;

    for (int i=1;i<=n;i++){
        if (r<i)
        {
            c=i;
            r=i;
        }
        else
            l[i]=min(l[2*c-i],r-i);

        while (i+l[i]+1<=n && i-l[i]-1>=1 && t[i+l[i]+1]==t[i-l[i]-1])
            ++l[i];

        if (i+l[i]>r)
        {
            c=i;
            r=i+l[i];
        }
        rez+=(l[i]+1)/2;
    }
    return rez;
}

int main()
{
    prep();
    g<<manach();
    return 0;
}