Cod sursa(job #2068794)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 18 noiembrie 2017 11:15:27
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 1000005;
char s[NMAX];
int LP[2 * NMAX], n;
int counter;

__attribute__((constructor))
void citire() {
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);

	fgets(s, NMAX, stdin);
	n = strlen(s);

	if(s[n - 1] == '\n') {
		s[n - 1] = 0;
		n--;
	}

	n = (n << 1) + 1;
}

__attribute__((destructor))
void solve() {
	int C = 1, R = 2;
	LP[0] = 0;
	LP[1] = 1;

	for (int i = 2; i < n; i++) {
		LP[i] = 0;

		if(R - i > 0) LP[i] = min(LP[(C << 1) - i], R - i);
		for(;(i + LP[i] < n && i - LP[i] > 0) && (((i + LP[i] + 1) & 1) == 0 || (s[(i + LP[i] + 1) >> 1] == s[(i - LP[i] - 1) >> 1])); LP[i]++);
		if(i + LP[i] > R) {
			R = i + LP[i];
			C = i;
		}
	}

	for (int i = 0; i < n; i++) counter += ceil(LP[i] / 2.0);

	printf("%d\n", counter);
}

int main() { }