Cod sursa(job #2068867)

Utilizator onescu.iancuOnescu Iancu onescu.iancu Data 18 noiembrie 2017 11:30:08
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int L[2000004], n;

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);

    char a[1000000];

    cin.getline(a, 1000000);
    n=strlen(a);
    n=n*2+1;

    int c=2;
    int r=3;

    L[0]=0;
    L[1]=1;

    long long nr=1;

    for(int i=2; i<n; i++)
    {
        int oglindit=c*2-i;
        L[i]=0;

        int dif=r-i;
        if(dif>0)
            L[i]=min(L[oglindit], dif);

        while ( ((i + L[i]) < n && (i - L[i]) > 0) && ( ((i + L[i] + 1) % 2 == 0) || (a[(i + L[i] + 1)/2] == a[(i - L[i] - 1)/2] )))
                L[i]++;

        if(i+L[i]>r)
        {
            c=i;
            r=i+L[i];
        }
        if(i%2==0)
            nr+=L[i]/2;
        else
            nr+=(L[i]+1)/2;
    }

    printf("%d", nr);
    return 0;
}