Cod sursa(job #1227504)

Utilizator iulishorIulian Popescu iulishor Data 10 septembrie 2014 19:26:20
Problema PScPld Scor 0
Compilator cpp Status done
Runda ubb_acm_2014_etapa_individuala_01 Marime 1.47 kb
#include <cstdio>
#include <string>
#define MaxN 1000005
#define infile "pscpld.in"
#define outfile "pscpld.out"

long long N, sol[MaxN], solp[MaxN], rez;
char a[MaxN];

void read()
{
	int i;

	scanf("%s", &a);
	N = strlen(a);
	for (i = N; i >= 1; i--)
		a[i] = a[i - 1];
}

long long minim(long long x, long long y)
{
	if (x<y)
		return x;
	return y;
}

void solvei()
{
	long long last = 1, l, i;

	for (i = 2; i<N; i++)
	{
		if (i<last + sol[last])
			sol[i] = minim(sol[last - (i - last)], last + sol[last] - i);

		l = sol[i];
		if (last + sol[last] <= i + sol[i])
		{
			last = i;
			while (i - l >= 1 && i + l <= N && a[i - l] == a[i + l])
				l++;
			if (l >= 1)
				sol[i] = l - 1;
		}
		rez += sol[i];
	}
}

void solvep()
{
	long long last = 1, l, i;
	if (a[1] == a[2])
		solp[1] = 1;

	for (i = 2; i<N; i++)
	{
		if (i<last + solp[last])
			solp[i] = minim(solp[last - (i - last)], last + solp[last] - i);

		l = solp[i];
		if (last + solp[last] <= i + solp[i])
		{
			last = i;
			while (i - l >= 1 && i + l + 1 <= N && a[i - l] == a[i + l + 1])
				l++;
			if (l >= 1)
				solp[i] = l - 1;
		}
		rez += solp[i];
	}

	for (i = 1; i<N; i++)
	if (a[i] == a[i + 1])
		solp[i]++, rez++;
}

void write()
{
	rez += N;
	printf("%lld\n", rez);
}

int main()
{
	freopen(infile, "r", stdin);
	freopen(outfile, "w", stdout);

	read();
	solvei();
	solvep();
	write();

	fclose(stdin);
	fclose(stdout);
	return 0;
}