Cod sursa(job #2868311)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 10 martie 2022 20:59:59
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
//const int dim = 2002;
ifstream fin ("pscpld.in");
ofstream fout("pscpld.out");
int lg[2000004];

int main()
{
    string a,s;
    fin>>a;
    int n=a.size();
    s+='@';
    for (int i=0;i<n;i++)
    {
        s+='$';
        s+=a[i];
    }
    s+="$#";
    int c=0,dr=0;
    lg[0]=1;
    for (int i=1;i<2*n+1;i++)
    {
        int ogl=2*c-i;
        lg[i]=min(lg[ogl], dr-i);
        while (s[i+lg[i]+1]==s[i-lg[i]-1])
            lg[i]++;
        if (i+lg[i]>dr)
        {
            dr=i+lg[i];
            c=i;
        }
    }
    long long sol=n;
    for (int i=0;i<2*n+1;i++)
    {
        lg[i]/=2;
        sol+=lg[i];
    }
    fout<<sol<<'\n';
}