Cod sursa(job #3237149)

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