Cod sursa(job #2722461)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 21:01:37
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 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 = 0, mij = 0;
	for (int i = 1; i <= n; ++i)  {
		if (i < r && i + m[mij - (i - mij)] < r)  {
			m[i] = m[mij - (i - mij)];
			continue;
		}
		int x = 0;
		if (i < r)
			x = r - i;
		while (s[i + x + 1] == s[i - x - 1])
			++x;
		if (i + x > r)
			r = i + x, mij = i;
		m[i] = x;
	}
}

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();
	long long ans = 0;
	for (int i = 1; i <= n; ++i)  {
		if (i & 1)  { //litera
			ans += (long long)(m[i] / 2 + 1);
		} else  { //*
			ans += (long long)((m[i] + 1) / 2);
		}
	}
	cout << ans;
	return 0;
}