Cod sursa(job #880733)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 17 februarie 2013 11:17:12
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb

#include <cstdio>

const int MAX_SIZE(1000010);

char v [MAX_SIZE];
char s [MAX_SIZE << 1];
int dp [MAX_SIZE << 1]; 
int vlength, length;

inline int min (int a, int b)
{
	return a < b ? a : b;
}

inline void read (void)
{
	std::freopen("pscpld.in","r",stdin);
	std::gets(v);
	s[0] = '$';
	int i, j;
	for (i = 0, j = 1 ; v[i] ; ++i, ++j)
	{
		s[j] = ' ';
		++j;
		s[j] = v[i];
	}
	s[j] = ' ';
	++j;
	s[j] = '#';
	length = j;
	vlength = i;
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("pscpld.out","w",stdout);
	long long result(0);
	for (int index(1) ; index <= length ; ++index)
		result += (dp[index] >> 1);
	std::printf("%lld",result + vlength);
	std::fclose(stdout);
}

inline void Manacher (void)
{
	int position, center(0), right(0), mirror;
	for (position = 1 ; position <= length ; ++position)
	{
		mirror = center - (position - center);
		dp[position] = position < right ? min(dp[mirror],right - position) : 0;
		while (s[position + dp[position] + 1] == s[position - dp[position] - 1])
			++dp[position];
		if (position + dp[position] > right)
		{
			right = position + dp[position];
			center = position;
		}
	}
}

int main (void)
{
	read();
	Manacher();
	print();
	return 0;
}