Cod sursa(job #1226695)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 6 septembrie 2014 20:15:22
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <cstring>
#define DIMN 2000005

using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

int n, len;

char s[DIMN], S[DIMN];

int P[DIMN];

inline int minim(int x, int y)  {
	return ( x < y ? x : y );
}

int main() {
	f.get(s, DIMN);
	len = strlen(s);
	for (int i = 1; i <= len; ++i) {
		S[2 * i - 1] = '#';
		S[2 * i] = s[i - 1];
	}
	n = len * 2 + 1;
	S[n] = '#';
	S[n + 1] = '\0';
	int C = 0, R = 0;
	for (int i = 2; i < n; ++i) {
		int i_mirror = 2 * C - i;
		P[i] = R>i ? minim(R - i, P[i_mirror]) : 0;
		while (i - P[i] - 1 > 0 && S[i - P[i] - 1] == S[i + P[i] + 1])
			++P[i];
		if (i + P[i] > R) {
			C = i;
			R = i + P[i];
		}
	}
	int SOL = 0;
	for (int i = 1; i <= n; ++i)
	if (S[i] == '#')
		SOL += P[i] / 2;
	else

		SOL += 1 + P[i] / 2;
	g << SOL;
	return 0;
}