Cod sursa(job #637455)

Utilizator ProtomanAndrei Purice Protoman Data 20 noiembrie 2011 14:32:50
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int lung[2000010];

int main()
{
	ifstream cin("pscpld.in");
	ofstream cout("pscpld.out");

	string str;
	cin >> str;
	if (!isalnum(str[str.size() - 1]))
		str.pop_back();

	str = " " + str;

	int maxGs = 0, mij = 0, sol = 0;
	for (int i = 1; i < str.size(); i++)
	{
		int x, y, loc;

		if (maxGs < i)
			mij = i, lung[2 * i - 1] = 1;

		loc = 2 * i - 1;
		lung[loc] = lung[mij - (loc - mij)];

		x = i - lung[loc] / 2 - 1, y = i + lung[loc] / 2 + 1;

		for (; x > 0 && y < str.size(); lung[loc] += 2, x--, y++)
			if (str[x] != str[y])
				break;

		sol += (lung[loc] + 1) / 2;
		if (maxGs < y - 1)
			maxGs = y - 1, mij = loc;

		loc = 2 * i;
		lung[loc] = lung[mij - (loc - mij)];

		x = i - lung[loc] / 2, y = i + lung[loc] / 2 + 1;
		
		for (; x > 0 && y < str.size(); lung[loc] += 2, x--, y++)
			if (str[x] != str[y])
				break;

		sol += lung[loc] / 2;
		if (maxGs < y - 1)
			maxGs = y - 1, mij = loc;
	}

	cout << sol;

	return 0;
}