Cod sursa(job #3155812)

Utilizator moldovan_robert_lolMoldovan Robert moldovan_robert_lol Data 9 octombrie 2023 19:27:34
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

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

std::string str;

std::vector<int> manacher_odd(const std::string& str) {
	std::vector<int> ret(str.size(),0);
	int l = 0, r = 0;

	for (int i = 0; i < str.size(); i++) {
		ret[i] = std::max(0,std::min(r-i,ret[l+r-i]));
		while (i-ret[i]>=0&&i+ret[i]<str.size()&&str[i-ret[i]]==str[i+ret[i]]) {
			++ret[i];
		}

		if (i+ret[i]>r) {
			l = i-ret[i];
			r = i+ret[i];
		}
	}

	return ret;
}

std::vector<int> manacher(const std::string& str) {
	std::string tmp = "#";
	for (const auto& i : str) {
		tmp += i;
		tmp += '#';
	}

	return manacher_odd(tmp);
}

int main() {
	fin >> str;
	std::vector<int> lps = manacher(str);

	int64_t ret = 0;
	for (int i = 0; i < lps.size(); i++) {
		ret += lps[i]/2;
		//std::cout << lps[i]/2 << " ";
	}
	//std::cout << "\n";

	fout << ret << "\n";
}