Cod sursa(job #1888362)

Utilizator calin1Serban Calin calin1 Data 22 februarie 2017 08:02:49
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000005

using namespace std;

char s[N], n;
long long v[N];

long long prelucrare()
{
    long long c = 1, dr = 2;

    v[0] = 0;
    v[1] = 1;

    for(long long i = 2 ; i <= 2 * n ; ++i)
    {
        if(i < dr)
        {
            v[i] = min(v[2 * c - i], dr - i);
        }

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

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

    long long nr = 0;

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

    return nr;
}

void citire()
{
    char tmp[1000005];

    gets(tmp);

    n = strlen(tmp);

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

    s[2 * n] = '#';

    printf("%lld",prelucrare());
}

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

    citire();

    return 0;
}