Cod sursa(job #1227519)

Utilizator iulishorIulian Popescu iulishor Data 10 septembrie 2014 19:36:08
Problema PScPld Scor 60
Compilator cpp Status done
Runda ubb_acm_2014_etapa_individuala_01 Marime 1.3 kb
#include<stdio.h>
#define fin  "pscpld.in"
#define fout "pscpld.out"
#define Nmax 2000001

#define FL
#define DBGx

int N, len[Nmax];
char v[Nmax];

long long ret;

int main()
{
	int i, j, a, b, poz;
	char ch;

	freopen(fin, "r", stdin);
#ifdef FL
	freopen(fout, "w", stdout);
#endif
	scanf("%c", &ch);

	N = 1; v[1] = ' ';

	while (ch != '\n')
	{
		++N;
		v[N] = ch;
		scanf("%c", &ch);
		++N;
		v[N] = ' ';
	}

	a = 1; b = 3;

	len[2] = 1;

	for (i = 3; i <= N; ++i)
	{
#ifdef DBG
		printf("%d: %d %d\n", i, a, b);
#endif
		if (i <= b)
		{
			poz = b - i;

			if (i + len[a + poz] >= b)
			{
				len[i] = b - i;
				b = i + len[i];
				a = i - len[i];
				while (v[a - 1] == v[b + 1] && a>1)
				{
					++len[i];
					++b;
					--a;
				}
			}
			else
				len[i] = len[a + poz];
		}
		else
		{
			len[i] = 0;
			a = i; b = i;
			while (v[a - 1] == v[b + 1] && a>1)
			{
				++len[i];
				++b;
				--a;
			}
		}
#ifdef DBG
		for (int j = 1; j <= N; ++j)
			printf("%c ", v[j]);
		printf("\n");
		for (int j = 1; j <= N; ++j)
			printf("%d ", len[j]);
		printf("\n\n");
#endif

	}


	for (i = 1; i <= N; ++i)
	if (v[i] == ' ')
		ret += (len[i] + 1) / 2;
	else
	{
		ret += len[i] / 2;
		++ret;
	}

	printf("%lld\n", ret);

	return 0;
}