Cod sursa(job #1883895)

Utilizator DanyBvGeorge-Daniel Gagiu DanyBv Data 18 februarie 2017 11:54:04
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <cstring>
#include <cstdio>

#define NMAX 1000001

using namespace std;

char   A[NMAX + 1];
int  LPS[2 * NMAX + 1], C, R, N;
long long nr;

void read()
{
    freopen("pscpld.in", "r", stdin);
    scanf("%s", A);
}

void solve()
{
    LPS[0] = 0;
    LPS[1] = 1;
    C = 1;
    R = 2;
    N = 2 * strlen(A) + 1;
    for(int i = 2; i < N; i++)
    {
        int ii = (C << 1) - i;
        if(R <= i)
            LPS[i] = 0;
        else
            LPS[i] = min(R - i, LPS[ii]);
        //Start expand
        while(i - LPS[i] > 0 && i + LPS[i] < N)
        {
            if((((i - LPS[i] - 1) & 1) == 0) || A[(i - LPS[i] - 1) / 2] == A[(i + LPS[i] + 1) / 2])
                LPS[i]++;
            else
                break;
        }
        //Stop expand
        if(i + LPS[i] > R)
        {
            R = i + LPS[i];
            C = i;
        }
    }
    for(int i = 0; i < N; i++)
        nr += ((LPS[i] + 1) >> 1);
}

void print()
{
    freopen("pscpld.out", "w", stdout);
    printf("%lld", nr);
}

int main()
{
    read();
    solve();
    print();
    return 0;
}