2017 - Palindromic Partitions

Explicación

El enfoque voraz (greedy) está implementado abajo. Vamos a inicializar dos strings (en este caso, valores de hash): uno construido con el $i$ -ésimo carácter y el otro con su complemento en la posición $n - i - 1$ . Recorreremos de izquierda a derecha, agregando caracteres de a uno a sus respectivos strings hasta que el string izquierdo sea igual al derecho, en cuyo caso podemos crear dos particiones. Para comprobar la igualdad de estos strings, usaremos hashing de strings.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll P = 69421;
const ll M = 1e9 + 9;
 
int main() {
	int tc;
	cin >> tc;
	while (tc--) {
		string s;
		cin >> s;
 
		int n = s.length();
		int ans = 0;
		int found = 0;  // -1 if no further strings can be found on both side
		int start = 0;  // index we start searching from
 
		while (found != -1) {
			ll hash_left = 0, hash_right = 0;
			found = -1;
			for (ll l = start, pw = 1; l < n / 2; l++, pw = (pw * P % M)) {
				hash_left = (hash_left * P + s[l]) % M;
				hash_right = (hash_right + pw * s[n - 1 - l]) % M;
				if (hash_left == hash_right) {
					found = l;
					break;
				}
			}
 
			// two partitions can be created with these two strings
			if (found != -1) {
				start = found + 1;
				ans += 2;
			}
		}
 
		// we have taken all the characters
		if (start * 2 == n) {
			cout << ans << endl;
		} else {
			cout << ans + 1 << endl;
		}
	}
}