Cod sursa(job #2068926)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 18 noiembrie 2017 11:38:09
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LMAX 1000005
using namespace std;

char s[LMAX];
long long counter = 0;
int Lp[2*LMAX + 1];

void MaicaTa()
{
    int len = strlen(s);

    if(len == 0)
        return;
    len = 2 * len + 1;

    Lp[0] = 0;
    Lp[1] = 1;
    int C = 1, R = 2;
    int iMirror;
    int expand = 0;
    int diff = -1;

    for(int i = 2; i < len; i++)
    {
        iMirror = 2 * C - 1;
        expand = 0;
        diff = R - i;

        if (diff > 0)
        {
            if(diff > 0)
                Lp[i] = min(Lp[iMirror], diff);
            while ( ((i + Lp[i]) < len && (i - Lp[i]) > 0) && ( ((i + Lp[i] + 1) % 2 == 0) || (s[(i + Lp[i] + 1)/2] == s[(i - Lp[i] - 1)/2] )))
            {
                Lp[i]++;
            }
        }
        if (i + Lp[i] > R)
        {
            C = i;
            R = i + Lp[i];
        }
    }
    for(int i = 1; i < len; i++)
        if(Lp[i] %2 == 0)
            counter += Lp[i] / 2;
        else
            counter += (Lp[i] / 2 + 1);
}

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

    scanf("%s", s);
    MaicaTa();
    printf("%lld", counter);
    return 0;
}