Cod sursa(job #2692008)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 31 decembrie 2020 01:48:10
Problema PScPld Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

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

int n, center, max_extended, nrpali[2000100];
string s = " *";

void brute_force_extend(int mid) {
	int st = mid - nrpali[mid] + 1;
	int dr = mid + nrpali[mid] - 1;
	while (st > 1 && dr < n) {
		if (s[st - 1] != s[dr + 1])
			break;
		st--;
		dr++;
		nrpali[mid]++;
	}
	if (dr > max_extended) {
		max_extended = dr;
		center = mid;
	}
}

int main() {
	fin.tie(0);fout.tie(0);
	ios::sync_with_stdio(0);
	
	string s_ini;
	fin >> s_ini;
	n = 2 * s_ini.length() + 1;
	for (int i = 0; i < (int)s_ini.length(); i++) {
		s += s_ini[i];
		s += "*";
	}
	
	for (int i = 1; i <= n; i++)
		nrpali[i] = 1;
		
	for (int i = 1; i <= n; i++) {
		if (i > max_extended) 
			brute_force_extend(i);
		else {
			int opus = center - (i - center);
			if (i + nrpali[opus] < max_extended) 
				nrpali[i] = nrpali[opus];
			else 
				brute_force_extend(i);
		}
	}
	
	ll total = 0;
	for (int i = 1; i <= n; i++)
		total += nrpali[i] / 2;
	fout << total;
	return 0;
}