Cod sursa(job #2722443)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 20:48:52
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int n;
int m[2000010];
string s, s_aux;

void manacher() {
	int r = 1, mij = 1;
	for (int i = 2; i <= n; ++i)  {
		int x = 0;
		if (i <= r)
			x = m[mij - (i - mij)];
		while (x < i && i + x + 1 <= n && s[i + x + 1] == s[i - x - 1])
			++x;
		m[i] = x;
		if (i + x > r)  {
			r = i + x;
			mij = i;
		}
	}
}

int main()  {
	cin >> s_aux;
	s = "#";
	for (int i = 0; i < s_aux.size() - 1; ++i)  {
		s += s_aux[i];
		s += "*";
	}
	s += s_aux[s_aux.size() - 1];
	s += "$";
	n = s.size() - 2;
	manacher();
	int ans = 0;
	for (int i = 1; i <= n; ++i)  {
		if (i & 1)  { //litera
			ans += m[i] / 2 + 1;
		} else  { //*
			ans += (m[i] + 1) / 2;
		}
	}
	cout << ans;
	return 0;
}