Cod sursa(job #1880237)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 15 februarie 2017 17:13:51
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100;

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;

    int nr = 1;

    for(int i = 2; i <= 2 * n; i++)
    {
        int j = c + (c - i);
//
//        if(i < dr)
//        {
//
//        }
//        else
//        {
            sirx[i] = 0;
        //}

        if(sir[i] == '#')
        {
            sirx[i]--;
        }
        else
        {
            nr++;
        }

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

        //sirx[i] -= 2;
    }

    printf("%d", nr);
}

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

    citire();
    manacher();

    return 0;
}