Cod sursa(job #3237150)

Utilizator Anul2024Anul2024 Anul2024 Data 5 iulie 2024 17:49:37
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
int n,i,l,poz,pozpal,lg[2000005];
char sir[2000005],sirc[2000005];
long long sol;
int main ()
{
    ///dbdedbd => dbd din dreapta = dbd din stanga => b din dreapta minim palindrom lg[stanga]
    fin>>sirc;
    n++;
    sir[n]='*';
    for (i=0; sirc[i]; i++)
    {
        sir[++n]=sirc[i];
        sir[++n]='*';
    }
    sir[n+1]=0;
    poz=0;
    for (i=1; i<=n; i++)
    {
        if (i<=poz)
            lg[i]=min (lg[pozpal-l+1+poz-i],poz-i+1);
        while (i-lg[i]>0&&i+lg[i]<=n&&sir[i-lg[i]]==sir[i+lg[i]])
            lg[i]++;
        if (i+lg[i]-1>poz)
        {
            l=lg[i];
            poz=i+lg[i]-1;
            pozpal=i;
        }
        sol+=lg[i]/2;
    }
    fout<<sol;
    return 0;
}