Cod sursa(job #2068888)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 18 noiembrie 2017 11:32:53
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 1000005

using namespace std;

char text[NMAX];
long long nrPalindroame, N, LP[2*NMAX];

void manacherAlgorithm()
{
    N = strlen(text);
    if(N == 0)
        return;
    N = 2 * N + 1; ///lungime LP - "adaugare stelute"
    LP[0] = 0;
    LP[1] = 1;
    int C = 1; ///centru
    int R = 2; ///raza de actiune
    int i = 0; ///pozitie
    int iMirror = 0; ///pozitie simetrica
    long long diff = -1; ///pentru iesire din raza
    //printf("%d %d ", LP[0], LP[1]);
    for(i = 2; i < N; ++i)
    {
        iMirror = 2 * C - i;
        LP[i] = 0;
        diff = R - i;

        ///daca se afla in raza de actiune
        if(diff > 0)
            LP[i] = min(LP[iMirror], diff);

        ///expansiune
        ///verificam daca ramane in limitele sirului [0, N]
        ///verificam daca expansiunea cade pe o steluta SAU sunt egale elementul pe care ne extindem cu simetricul lui
        while(((i + LP[i] + 1) % 2 == 0 || (text[(i + LP[i] + 1)/2] == text[(i - LP[i] - 1)/2]))
              && ((i + LP[i] < N) && (i - LP[i] > 0)))
                LP[i]++;

        ///mutam centrul
        if(i + LP[i] > R)
        {
            C = R;
            R = i + LP[i];
        }
        //printf("%d ", LP[i]);
    }
    //printf("\n");
}

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    scanf("%s", text);
    manacherAlgorithm();
    for(int i=1; i<=N; ++i)
        if(LP[i] == 1)
            nrPalindroame++;
        else if(LP[i] % 2 == 1)
            nrPalindroame += LP[i]/2 + 1;
        else if(LP[i] != 0)
            nrPalindroame += LP[i]/2;

    printf("%lld", nrPalindroame);
    return 0;
}