Cod sursa(job #2510631)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 16 decembrie 2019 23:35:06
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#define N 1000004
#include <cstring>

using namespace std;

char ch[2*N],s[N];
int lp[2*N];

int main()
{
    ifstream f("pscpld.in");
    ofstream g("pscpld.out");
    int n,c,lg,exp,dr,i,ii;
    f>>ch;
    n=strlen(ch);
    lg=-1;
    for( i=0;i<n;++i)
    {
        s[++lg]='!';
        s[++lg]=ch[i];
    }
    s[++lg]='!';
    long long ss=n;
    c=1,dr=2;
    lp[1]=1;
    for(i=2;i<=lg;++i)
    {
        ii=c-(i-c);
        exp=0;
        if(dr<=i)
            exp=1;
        else
        {
            if(lp[ii]<dr-i)///se gaseste in palindromul mare, dar nu e prefix
                lp[i]=lp[ii];
            else
                if(lp[ii]==dr-i)///e prefix al palindromului mare
                    lp[i]=lp[ii],exp=1;
                else
                    if(lp[ii]>dr-i)///se afla in exteriorul palindromului
                        lp[i]=dr-i,exp=1;
        }
        if(exp)
        {
            while(i-lp[i]-1>=0 && i+lp[i]+1<=lg)
                if((i-lp[i])%2!=0)
                    ++lp[i];
                else
                    if(s[i-lp[i]-1]==s[i+lp[i]+1])
                        ++lp[i];
                    else
                        break;
        }
        if(dr<i+lp[i])
            dr=i+lp[i],c=i;
        ss=ss+(long long)lp[i]/2;
    }
    g<<ss<<'\n';
    f.close();
    g.close();
    return 0;
}