Palinilap

Explicación

Cuando cambiamos un carácter, todas las subcadenas pueden hacer una de 3 cosas:

Dejar de ser un palíndromo
Convertirse en un palíndromo (los llamaremos “palíndromos wannabe”)
Nada (no se ven afectadas en absoluto)

Si hallamos el número de subcadenas que están en cada estado para un cierto cambio, ¡ya casi tenemos la respuesta!

Palíndromos iniciales

Para hallar todos los palíndromos de nuestro string, iteramos sobre todos los centros y vemos hasta dónde podemos extender los lados manteniendo el string como palíndromo.

Observemos que si sabemos que una extensión de, por ejemplo, 5 caracteres nos da un palíndromo, sabemos que una extensión de 4 caracteres también nos daría un palíndromo. De forma similar, si sabemos que una extensión de 7 caracteres no da un palíndromo, una extensión de 8 caracteres tampoco funcionará. Así, podemos hacer búsqueda binaria sobre la longitud máxima a la que podemos extender los lados.

Para comprobar rápido si una subcadena es un palíndromo, obtenemos el hash rolling de un string y de su reverso y comprobamos si ambos dan el mismo hash.

Para todos estos palíndromos, un cambio del carácter en cualquier lado (excepto el centro) provocaría la destrucción del palíndromo.

Tomemos este palíndromo: $s=\text{youruoy}$ . Si dejamos que $\texttt{bad}[i]$ sea el número de palíndromos (relativos a este centro) que se destruirían si se cambiara $s_i$ , este sería el arreglo:

[1,2,3,0,3,2,1]

Nótese cómo los números aumentan hasta la mitad de la longitud del palíndromo, y luego decrecen de vuelta a 1. El centro de $\texttt{bad}$ es 0 porque su posición no cambia al invertir.

Para todos los centros, hay que sumar todos sus $\texttt{bad}$ para obtener el número total de palíndromos destruidos por cada carácter cambiado.

Para hacer esto, hay que sumar de forma eficiente secuencias consecutivas de números a un arreglo, lo cual podemos hacer con dos iteraciones de un arreglo de diferencias.

Palíndromos wannabe

Como podemos cambiar un carácter, también debemos hallar todas las subcadenas que están a solo un carácter de convertirse en palíndromo, como estos strings:

$\text{baaac}$
$\text{abcdeba}$

Después de obtener la extensión máxima de la búsqueda binaria que acabamos de discutir, podemos ejecutar otra búsqueda binaria para hallar la extensión máxima con un carácter reemplazado. Podemos reemplazar un carácter a la izquierda o a la derecha con el mismo resultado: por ejemplo, reemplazar $e$ por $c$ o $c$ por $e$ en el segundo string daría los mismos resultados para ese wannabe.

Esta vez, para comparar dos strings, necesitamos poder obtener un hash con un carácter reemplazado también, así que hace falta una pequeña modificación de nuestra función de hashing.

Juntando todo

Con ambas búsquedas binarias, podemos obtener las dos estructuras finales que necesitamos:

$\texttt{bad}[i]$ , el número de palíndromos arruinados si cambiamos el carácter $i$
$\texttt{good}[i][c]$ , el número de palíndromos nuevos si cambiamos el carácter $i$ a $c$

Ahora iteramos sobre todos los caracteres cambiados y tomamos el mejor cambio para nuestra respuesta final.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

C++


#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <map>
#include <vector>
 
using namespace std;
 
// BeginCodeSnip{String Hashing}
/** source: https://usaco.guide/gold/modular */
long long pow_mod(long long x, long long n, long long mod) {
	assert(n >= 0);
	x %= mod;
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % mod; }
		x = x * x % mod;
		n /= 2;
	}
	return res;
}
 
class HashedString {
  private:
	static const long long MOD = 1e9 + 9;
	static const long long POW = 101;
 
	static vector<long long> pow;
	static vector<long long> mod_inv;
 
	const string &s;
	vector<long long> p_hash;
 
  public:
	HashedString(const string &s) : s(s), p_hash(s.size() + 1) {
		while (pow.size() < s.size()) {
			pow.push_back((pow.back() * POW) % MOD);
			mod_inv.push_back(pow_mod(pow.back(), MOD - 2, MOD));
		}
 
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = (p_hash[i] + s[i] * pow[i] % MOD) % MOD;
		}
	}
 
	long long hash(int from, int to) {
		long long pref = (p_hash[to + 1] - p_hash[from] + MOD) % MOD;
		return pref * mod_inv[from] % MOD;
	}
 
	/** @return hash de la subcadena con un carácter dado reemplazado */
	long long hash(int from, int to, const pair<int, char> &rep) {
		long long pref = p_hash[to + 1] - p_hash[from];
		if (from <= rep.first && rep.first <= to) {
			pref += rep.second * pow[rep.first] - s[rep.first] * pow[rep.first];
		}
		return (pref % MOD + MOD) * mod_inv[from] % MOD;
	}
};
vector<long long> HashedString::pow = {1};
vector<long long> HashedString::mod_inv = {1};
// EndCodeSnip
 
/**
 * @return el mayor número en [lo, hi] tal que check se cumple.
 * si ningún número del rango funciona, se devuelve -1
 */
int last_true(int lo, int hi, function<bool(int)> check) {
	int valid = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) {
			lo = mid + 1;
			valid = mid;
		} else {
			hi = mid - 1;
		}
	}
	return valid;
}
 
/**
 * @return el arreglo resultante cuando se realizan las operaciones en los rangos
 * @param ranges en cada uno de los rangos de esta variable, se suman números
 * consecutivos empezando desde 1 al subarreglo. por ejemplo, [0, 3] sumaría
 * los números 1, 2, 3 y 4 a los primeros 4 elementos del rango [0, 3].
 */
vector<long long> range_res(int size, const vector<pair<int, int>> &ranges) {
	vector<long long> arr(size + 1);
	for (const auto &[a, b] : ranges) {
		arr[a]++;
		arr[b + 1]--;
	}
	for (int i = 1; i < size; i++) { arr[i] += arr[i - 1]; }
	for (const auto &[a, b] : ranges) { arr[b + 1] -= b - a + 1; }
	for (int i = 1; i < size; i++) { arr[i] += arr[i - 1]; }
	arr.pop_back();
	return arr;
}
 
int main() {
	string str;
	cin >> str;
	int len = str.size();  // abreviatura
 
	string rev_str = str;
	reverse(rev_str.begin(), rev_str.end());
	HashedString h_str(str), h_rev_str(rev_str);
 
	// comprueba si una subcadena es un palíndromo
	auto is_pal = [&](int from, int to) {
		return h_str.hash(from, to) == h_rev_str.hash(len - to - 1, len - from - 1);
	};
	// comprueba si una subcadena es un palíndromo con un carácter reemplazado
	auto is_pal_rep = [&](int from, int to, pair<int, char> rep) {
		pair<int, char> r_rep{len - rep.first - 1, rep.second};
		return h_str.hash(from, to, rep) ==
		       h_rev_str.hash(len - to - 1, len - from - 1, r_rep);
	};
 
	function<bool(int)> check;
	vector<map<char, long long>> good(len);
	// los rangos que hay que sumar a nuestro arreglo bad
	vector<pair<int, int>> removal1, removal2;
	long long init_amt = 0;  // la cantidad inicial de palíndromos
	for (int c = 0; c < len; c++) {
		// primero comprobamos los palíndromos de longitud impar relativos a c
		int most = min(c, len - c - 1);  // lo máximo que podemos extender desde la posición c
		check = [&](int d) { return is_pal(c - d, c + d); };
		int raw_pal = last_true(0, most, check);
		init_amt += raw_pal + 1;
		if (raw_pal > 0) {
			removal1.push_back({c - raw_pal, c - 1});
			removal2.push_back({c + 1, c + raw_pal});
		}
 
		pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal - 1]};
		check = [&](int d) { return is_pal_rep(c - d, c + d, rep); };
		int rep_pal = last_true(raw_pal + 1, most, check);
		if (rep_pal != -1) {
			good[rep.first][rep.second] += rep_pal - raw_pal;
			good[c - raw_pal - 1][str[c + raw_pal + 1]] += rep_pal - raw_pal;
		}
 
		// y luego los palíndromos de longitud par
		if (c < len - 1) {
			int most = min(c + 1, len - c - 1);
			check = [&](int d) { return is_pal(c - d + 1, c + d); };
			int raw_pal = last_true(0, most, check);
			init_amt += raw_pal;
			if (raw_pal > 0) {
				removal1.push_back({c - raw_pal + 1, c});
				removal2.push_back({c + 1, c + raw_pal});
			}
 
			pair<int, char> rep = {c + raw_pal + 1, str[c - raw_pal]};
			check = [&](int d) { return is_pal_rep(c - d + 1, c + d, rep); };
			int rep_pal = last_true(raw_pal + 1, most, check);
			if (rep_pal != -1) {
				good[rep.first][rep.second] += rep_pal - raw_pal;
				good[c - raw_pal][str[c + raw_pal + 1]] += rep_pal - raw_pal;
			}
		}
	}
 
	for (pair<int, int> &r : removal2) { r = {len - r.second - 1, len - r.first - 1}; }
	// estos dos combinados dan el arreglo bad enunciado en el análisis
	vector<long long> bad1 = range_res(len, removal1);
	vector<long long> bad2 = range_res(len, removal2);
	std::reverse(bad2.begin(), bad2.end());
 
	long long max_weight = init_amt;
	for (int i = 0; i < len; i++) {
		long long max_inc = 0;
		for (const auto &[_, i] : good[i]) { max_inc = max(max_inc, i); }
		max_weight = max(max_weight, init_amt + max_inc - bad1[i] - bad2[i]);
	}
 
	cout << max_weight << endl;
}