Fullmetal Alchemist II

Explicación

El problema nos pide hallar la longitud del string más corto que contiene un conjunto dado de $N$ strings como subcadenas. Esta es una variante del problema Shortest Common Superstring. Como $N$ es pequeño, podemos usar un enfoque de fuerza bruta con permutaciones combinado con hashing eficiente de strings.

Paso 1: filtrar strings redundantes

Primero, obsérvese que si un string $A$ es subcadena de otro string $B$ , nunca hace falta preocuparnos explícitamente de “cubrir” $A$ . Si nuestro string resultado contiene $B$ , automáticamente contiene $A$ . Por lo tanto, podemos eliminar todos los strings que son subcadenas de otros strings del conjunto de entrada.

Para comprobar de forma eficiente si el string $A$ es subcadena de $B$ , podemos usar hashes rolling. Calculamos el hash de $A$ y lo comparamos contra los hashes de todas las subcadenas de $B$ de longitud $|A|$ .

Paso 2: calcular solapamientos

Una vez que tenemos un conjunto filtrado de strings únicos, hay que disponerlos en un orden específico. Cuando concatenamos el string $A$ seguido del string $B$ , podemos fusionarlos si un sufijo de $A$ coincide con un prefijo de $B$ . Para minimizar la longitud total, queremos maximizar este solapamiento.

Sea $\texttt{overlap}(A, B)$ la longitud del sufijo más largo de $A$ que es igual a un prefijo de $B$ . El costo (caracteres adicionales necesarios) de anexar $B$ después de $A$ es $|B| - \texttt{overlap}(A, B)$ .

Podemos precomputar estos costos de solapamiento para cada par de strings $(i, j)$ . Usando hashes rolling, podemos comprobar la igualdad de sufijos y prefijos en $\mathcal{O}(1)$ después de un preprocesamiento $\mathcal{O}(L)$ .

Paso 3: hallar la mejor permutación

Después de preprocesar los solapamientos, el problema se reduce a hallar un orden (permutación) de los strings $S_{p_1}, S_{p_2}, \dots, S_{p_k}$ tal que la longitud total se minimice.

La longitud total para una permutación específica es:

|S_{p_1}| + \sum_{i=2}^{k} (|S_{p_i}| - \texttt{overlap}(S_{p_{i-1}}, S_{p_i}))

Como $N$ es pequeño (el tipo de problema sugiere que es alrededor de 10 o menos), podemos iterar sobre las $N!$ permutaciones usando next_permutation y calcular la longitud total de cada una, quedándonos con el mínimo.

Implementación

Complejidad temporal: $\mathcal{O}(N^2 L + N! \cdot N)$

C++


#include <bits/stdc++.h>
 
using namespace std;
 
// BeginCodeSnip{HashedString}
class HashedString {
  private:
	// Change M and B if needed for collision avoidance
	static const long long M = 1e9 + 9;
	static const long long B = 9973;
 
	// pow[i] contains B^i % M
	static vector<long long> pow;
 
	// p_hash[i] is the hash of the first i characters of the given string
	vector<long long> p_hash;
 
  public:
	int size;
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }
		this->size = s.size();
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
		}
	}
 
	long long get_hash(int start, int end) const {
		long long raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
		return (raw_val % M + M) % M;
	}
};
vector<long long> HashedString::pow = {1};
// EndCodeSnip
 
// Checks if A is a substring of B
bool isSubstr(const HashedString &a, const HashedString &b) {
	int l = 0, r = a.size - 1;
	while (r < b.size) {
		if (a.get_hash(0, a.size - 1) == b.get_hash(l, r)) { return true; }
		l++;
		r++;
	}
	return false;
}
 
// Calculates the length added by appending b to a (Size of b - (longest suffix of a
// matching a prefix of b))
int getMergeLength(const HashedString &a, const HashedString &b) {
	int r = a.size - 1;
	int mx = 0;
	// Check overlaps of length k
	for (int k = 0; k < b.size; ++k) {
		if (r < 0) { break; }
		// Compare the hash of the suffix of a and the prefix of b with length k+1
		if (a.get_hash(r, a.size - 1) == b.get_hash(0, k)) { mx = k + 1; }
		r--;
	}
	// We only need to add the non-overlapping part of b
	return b.size - mx;
}
 
int main() {
	int n;
	cin >> n;
	vector<HashedString> v;
	vector<HashedString> tmp;
	vector<int> idx;
 
	// Read input
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		v.push_back(HashedString(s));
	}
 
	// Step 1: Remove unneeded strings (those that are substrings of others)
	sort(v.begin(), v.end(),
	     [](const HashedString &a, const HashedString &b) { return a.size < b.size; });
	for (int i = 0; i < v.size(); ++i) {
		bool f = true;
		for (int j = i + 1; j < v.size(); ++j) {
			// If v[i] is smaller and is a substring of v[j], we don't need v[i]
			if (i == j || v[i].size > v[j].size) { continue; }
			if (isSubstr(v[i], v[j])) {
				f = false;
				break;
			}
		}
		if (f) { tmp.push_back(v[i]); }
	}
	v = tmp;
	n = v.size();
 
	// Step 2: Precompute merge costs
	// merge_length[i][j] stores the cost to append v[j] after v[i]
	vector<vector<int>> merge_length(n, vector<int>(n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) { continue; }
			merge_length[i][j] = getMergeLength(v[i], v[j]);
		}
	}
 
	// Initialize permutation indices
	for (int i = 0; i < n; ++i) { idx.push_back(i); }
 
	// Step 3: Try all permutations to find the minimal total length
	int ans = INT32_MAX;
	do {
		// Start with the full length of the first string
		int current_len = v[idx[0]].size;
		for (int i = 1; i < n; ++i) {
			// Add the cost of appending the next string in the sequence
			current_len += merge_length[idx[i - 1]][idx[i]];
		}
		ans = min(ans, current_len);
	} while (next_permutation(idx.begin(), idx.end()));
 
	cout << ans << '\n';
}