Cod sursa(job #1832566)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 20 decembrie 2016 13:26:56
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <string>
#include <fstream>
#include <cstring>
#define NMAX 2000000
using namespace std;

char c[NMAX + 1000];
char cit[NMAX / 2 + 1000];
int pal[NMAX + 1000]; /// cel mai lung pal cu centrul in x
int n, m, piv, l;

int main()
{
	ifstream in("pscpld.in");
	in >> cit;
	m = strlen(cit);
	for (int i(0); i < m; i++) {
		c[2 * i] = cit[i];
		c[2 * i + 1] = '$';
	}
	n = 2 * m - 1;

	piv = -1, l = -1;

	for (int i(0); i < n; i++) {
		if (i > piv + l) {
			piv = i;
			l = 0;
			while (i - l - 1 >= 0 && i + l + 1 < n && c[i - l - 1] == c[i + l + 1])
				l++;
			pal[i] = l;
		}
		else {
			int p(pal[2 * piv - i]);
			if (i + p > piv + l)
				pal[i] = piv + l - i;
			else if (i + p < piv + l)
				pal[i] = p;
			else {
				piv = i, l = p;
				while (i - l - 1 >= 0 && i + l + 1 < n && c[i - l - 1] == c[i + l + 1])
					l++;
				pal[i] = l;
			}
		}
	}
	long long rez(0);

	for (int i(0); i < n; i++) {
		if (c[i] == '$')
			rez += 1ll * (pal[i] + 1) / 2;
		else
			rez += 1ll + 1ll * pal[i] / 2;
	}

	ofstream out("pscpld.out");
	
	out << rez;

	return 0;
}