Cod sursa(job #2068868)

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

char s[LMAX];
long long counter = 0;

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

	if(len == 0)
		return;
    len = 2 * len + 1;
    int Lp[len];
    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;
		exp = 0;
        diff = R - i;

        if (diff > 0)
        {
        	if(Lp[iMirror] < diff)
                Lp[i] = Lp[iMirror];
            else
				if(Lp[iMirror] == diff && i == len - 1)
                Lp[i] = Lp[iMirror];
            else
            if(Lp[iMirror] == diff && i < len - 1)
            {
                    Lp[i] = Lp[iMirror];
                    expand = 1;
            }
            else
			if(Lp[iMirror] > diff)
            {
                Lp[i] = diff;
                expand = 1;
            }
        }
        else
		{
			Lp[i] = 0;
			expand = 1;
		}

		if(expand == 1)
		{
            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]++;
            }
		}
	}
	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;
}