Cod sursa(job #3220749)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 4 aprilie 2024 18:48:05
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<int> menacher(string s) {
	int l = 0, r = 0;
	vector<int> man(s.size());
	for(int i = 0; i < (int)s.size(); i++) {
		man[i] = max(0, min(r-i, man[l+r-i]));
		while(i - man[i] >= 0 && i + man[i] < (int)s.size() && s[i - man[i]] == s[i + man[i]]) {
			man[i]++;
		}
		if(i + man[i] > r) { 
			l = i - man[i];
			r = i + man[i];
		}
	}
	return man;
}

int main() {
	string s;
	in >> s;

	string t;
	for(auto c : s) {
		t += string("#") + c;
	}
	t += "#";

	vector<int> man = menacher(t);

	int cnt = 0;
	for(int i = 0; i < (int)man.size(); i++) {
		cnt += man[i] / 2;
	}
	out << cnt;

	return 0;
}