Cod sursa(job #2272179)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 29 octombrie 2018 19:49:09
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream fi("pscpld.in");
ofstream fo("pscpld.out");
int n,x,i,y,poz,sf,Lp[100005],j,nrb;
long long rez;
char A[100005],B[200015];
int main()
{
    fi>>(A+1);
    n=strlen(A+1);
    poz=0;
    sf=0;
    for(i=1; i<=n; i++)
    {
        if(i>sf)
        {
            for(j=1; j<=min(i-1,n-i); j++)
                if(A[i-j]!=A[i+j])
                    break;
            Lp[i]=j;
            poz=i;
            sf=i+j-1;
        }
        else
        {
            if((poz-(i-poz))-Lp[poz-(i-poz)]+1>poz-Lp[poz]+1)
                Lp[i]=Lp[poz-(i-poz)];
            else
            {
                for(j=sf-i+1; j<=min(i-1,n-i); j++)
                    if(A[i-j]!=A[i+j])
                        break;
                Lp[i]=j;
                poz=i;
                sf=i+j-1;
            }
        }
        rez+=(1LL*Lp[i]);
    }
    for(i=1; i<=n; i++)
    {
        B[++nrb]='*';
        B[++nrb]=A[i];
    }
    B[++nrb]='*';
    n=nrb;
    poz=0;
    sf=0;
    for(i=1; i<=n; i++)
    {
        if(B[i]!='*')
            continue;
        if(i>sf)
        {
            for(j=1; j<=min(i-1,n-i); j++)
                if(B[i-j]!=B[i+j])
                    break;
            Lp[i]=j;
            poz=i;
            sf=i+j-1;
        }
        else
        {
            if((poz-(i-poz))-Lp[poz-(i-poz)]+1>poz-Lp[poz]+1)
                Lp[i]=Lp[poz-(i-poz)];
            else
            {
                for(j=sf-i+1; j<=min(i-1,n-i); j++)
                    if(B[i-j]!=B[i+j])
                        break;
                Lp[i]=j;
                poz=i;
                sf=i+j-1;
            }
        }
        rez+=(1LL*Lp[i]/2LL);
    }
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}