Cod sursa(job #3333122)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 11 ianuarie 2026 11:39:39
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <fstream>
#define ll long long

using namespace std;

const int nmax = 2e6 + 5;
const string txt = "pscpld";

ifstream f(txt + ".in");
ofstream g(txt + ".out");

int p[nmax], ans;
string s;

int main()
{
	char c; s += '@'; s += '#';
	while (f >> c)
		s += c, s += '#';
	s += '!';

	int l = 0, r = 0, n = s.size() - 1, ans = 0;
	for (int i = 1; i < n; i++)
	{
		int poz = l + r - i;
		if (i < r) p[i] = min(r - i, p[poz]);
		while (s[i - p[i] - 1] == s[i + p[i] + 1]) p[i]++;

		if (i + p[i] > r)
			l = i - p[i], r = i + p[i];
		
		ans += (p[i] + 1) / 2;
	}

	g << ans;
	return 0;
}