Cod sursa(job #2767187)

Utilizator alexmorosanuMorosanu Alexandru alexmorosanu Data 5 august 2021 10:49:52
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
long long s;
int n,i,l,r,k,a[1000011],b[1000011];
char c[1000011];
int main()
{
    f>>c;
    n=strlen(c);
    for(i=0,l=0,r=-1;i<n;i++)
    {
        if(i>r)
            k=1;
        else
            k=min(a[l+r-i],r-i+1);
        while(i-k>=0 && i+k<n && c[i-k]==c[i+k])
             k++;
            a[i]=k--;
            if(i+k>r)
            {
                l=i-k;
                r=i+k;
            }
        s=s+max(a[i],0);
    }
    for(i=0,l=0,r=-1;i<n;i++)
    {
        if(i>r)
            k=0;
        else
            k=min(b[l+r-i+1],r-i+1);
        while(i-k>=0 && i+k<n && c[i-k-1]==c[i+k])
         k++;
            b[i]=k--;
            if(i+k>r)
            {
                l=i-k-1;
                r=i+k;
            }
        s=s+max(b[i],0);
    }
    g<<s;
    return 0;
}