Cod sursa(job #1887763)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 21 februarie 2017 19:12:59
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2000005;

int n;
char sir[2 * N];
int sirx[2 * N];

void citire()
{
    char tmp[N + 1];

    fgets(tmp, N + 1, stdin);
    n = strlen(tmp);
    tmp[n - 1] = 0;
    n--;

    sir[0] = '#';

    for(int i = 1; i <= 2 * n; i += 2)
    {
        sir[i] = tmp[i / 2];
        sir[i + 1] = '#';
    }
}

void manacher()
{
    sirx[0] = 0;
    sirx[1] = 1;

    int c = 0;
    int dr = 0;

    for(int i = 2; i <= 2 * n; i++)
    {
        int j = c + (c - i);

        if(i < dr)
        {
            if(dr - i < sirx[j])
            {
                sirx[i] = dr - i;
            }
            else
            {
                sirx[i] = sirx[j];
            }
        }
        else
        {
            sirx[i] = 0;
        }

        while(i - sirx[i] - 1 >= 0 && i + sirx[i] + 1 <= 2 * n && sir[i - sirx[i] - 1] == sir[i + sirx[i] + 1])
        {
            sirx[i]++;
        }

        if(sirx[i] + i > dr)
        {
            dr = i + sirx[i];
            c = i;
        }
    }

    long long nr = 0;

    for(int i = 1; i <= 2 * n; i++)
    {
        if(sirx[i] % 2 == 0)
        {
            nr += sirx[i] / 2;
        }
        else
        {
            nr += sirx[i] / 2 + 1;
        }
    }

    printf("%lld", nr);
}

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

    citire();
    manacher();

    return 0;
}