Cod sursa(job #2068881)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 18 noiembrie 2017 11:31:40
Problema PScPld Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;
string txt;
int lp[2000004];
int main()
{
    freopen("pscpld.in","r",stdin);
    freopen("pscpld.out","w",stdout);
    getline(cin,txt);
    int leg;
    long long rez=1;
    leg=txt.length();
    leg=2*leg+1;
    lp[1]=1;
    int c=1,r=2;
    int sim,dd;
    for(int i=2; i<leg; ++i)
    {
        sim=2*c-i;
        dd=r-i;
        if(dd>0)
            lp[i]=min(lp[sim],dd);
        while(i+lp[i]<leg && i-lp[i]>0
                && ((i+lp[i]+1)%2==0 || txt[(i+lp[i]+1)/2]==txt[(i-lp[i]-1)/2]))
        {
            lp[i]++;
        }
        if(i+lp[i]>r)
        {
            c=i;
            r=lp[i]+i;
        }
        if(i%2==1)
            rez=rez+(lp[i]+1)/2;
        else
            rez=rez+lp[i]/2;
    }
    cout<<rez;
    return 0;
}