Cod sursa(job #1227566)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 10 septembrie 2014 20:36:39
Problema PScPld Scor 0
Compilator cpp Status done
Runda ubb_acm_2014_etapa_individuala_01 Marime 1.87 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");

#define b1 257
#define M1 10007
#define M2 11003
#define NMAX 1000002

int i, j, N;
int ANS;

char s[NMAX];

int pw1[NMAX];
int pw2[NMAX];
int h1[NMAX];
int h2[NMAX];
int h1_r[NMAX];
int h2_r[NMAX];

inline int BinarySearch(int p, int L, int h, int r) {
	int left = 1, right = L, m, k, w, last = 0;
	while (left <= right) {
		m = (left + right) >> 1;
		k = p - m - 1;
		w = p + r + m + 1;
		if (((h1[p - 1] - (pw1[p - 1 - k] * h1[k]) % M1) + M1) % M1 == ((h1_r[p + 1 + r] - (pw1[w - 1 - (p + r)] * h1_r[w]) % M1) + M1) % M1 &&
			((h2[p - 1] - (pw2[p - 1 - k] * h2[k]) % M2) + M2) % M2 == ((h2_r[p + 1 + r] - (pw2[w - 1 - (p + r)] * h2_r[w]) % M2) + M2) % M2) {
			last = m;
			if (h == 1) 
				left = m + 1;
			else 
				right = m - 1;
		}
		else {
			if (h == 1)
				right = m - 1;
			else 
				left = m + 1;
		}
	}
	return last;
}

int main() {
	fin >> (s + 1);
	N = strlen(s + 1);
	pw1[0] = pw2[0] = 1;
	for (i = 1, j = N; i <= N && j >= 1; ++i, --j) {
		pw1[i] = (pw1[i - 1] * b1) % M1;
		pw2[i] = (pw2[i - 1] * b1) % M2;
		h1[i] = (h1[i - 1] * b1 + s[i]) % M1;
		h2[i] = (h2[i - 1] * b1 + s[i]) % M2;
		h1_r[j] = (h1_r[j + 1] * b1 + s[j]) % M1;
		h2_r[j] = (h2_r[j + 1] * b1 + s[j]) % M2;
	}
	int top, bot;
	for (i = 1; i < N; ++i) 
		if (s[i] == s[i + 1]) ++ANS;
	for (i = 2; i < N; ++i) {
		top = BinarySearch(i, min(i - 1, N - i), 1, 0);
		bot = BinarySearch(i, min(i - 1, N - i), 0, 0);
		if (top && bot) 
			ANS += (top - bot + 1);
		if (s[i] == s[i + 1]) {
			top = BinarySearch(i, min(i - 1, N - (i + 1)), 1, 1);
			bot = BinarySearch(i, min(i - 1, N - (i + 1)), 0, 1);
			if (top && bot) 
				ANS += (top - bot + 1);
		}
	}
	fout << ANS + N << '\n';
	return 0;
}