Cod sursa(job #2068800)

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

using namespace std;

int nr[1000000];

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

    char a[1000000];
    int L[100000], n;

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

    int c=2;
    int r=3;

    L[0]=0;
    L[1]=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];
        }
    }

    int k=2;

    while(k<n)
        {
            for(int i=0; i<n; i++)
                if(L[i]==k)
                    nr[k]++;
            k++;
        }

    int counter=0;
    for(int i=0; i<n; i++)
        if(nr[i]>0)
            counter+=nr[i];
    printf("%d", counter+(n-1)/2);
    return 0;
}