Cod sursa(job #1880735)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 15 februarie 2017 21:33:01
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define NMax 1000005

using namespace std;

int lps[2*NMax], N ;
char s[NMax];

void Read()
{
    scanf("%s", &s);
}

void Solve()
{
    int C=1, R=0, ii, N;
    lps[0]=0;
    lps[1]=1;
    N=strlen(s);
    N=2*N+1;

    for(int i=2; i<N; ++i)
    {
        ii=2*C-i;
        int dif=R-i;

        lps[i]=0;

        if(dif>0)
            lps[i]=min(dif,lps[ii]);

        while ( ((i + lps[i]) < N && (i - lps[i]) > 0) &&
			( ((i + lps[i] + 1) % 2 == 0) ||
			(s[(i + lps[i] + 1)/2] == s[(i - lps[i] - 1)/2] )))
                lps[i]++;

        if(i+lps[i] > R)
        {
            C=i;
            R=i+lps[i];
        }

    }

    long long Sum=0;

    for(int i=1; i<=N-1; ++i)
    {
        if(lps[i]%2==0)
            Sum+=lps[i]/2;

        else
            Sum+=lps[i]/2+1;
    }

    printf("%lld\n", Sum);
}



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

    Read();
    Solve();

    return 0;
}