Skip to Content
CTRL K

Pattern Matching

Análisis oficial (C++) 

Explicación

Se nos dan patrones de longitud kk que contienen letras minúsculas y _, y consultas consistentes en strings con un índice de patrón requerido. Para que un string coincida con un patrón, todos los índices que no son _ en el patrón deben coincidir con el string.

Para cada consulta (s,p)(s, p), sea SS el conjunto de todos los patrones que coinciden con ss. El patrón pp debe aparecer antes que todos los demás patrones de SS en el ordenamiento. Cada requisito es por lo tanto una restricción de precedencia, donde pp debe ir antes que cualquier otro elemento de SS. Las modelamos como aristas dirigidas p→xp \to x, donde xx es cualquier elemento de SS distinto de pp.

Un ordenamiento válido corresponde entonces a un orden topológico del grafo resultante: si las restricciones son consistentes, cualquier orden topológico sirve, ya que cada arista p→xp \to x garantiza que pp aparece antes que cualquier otro patrón que coincide con ese string de consulta, haciendo que pp sea el primer patrón coincidente como se requiere. Si dos restricciones se contradicen (p. ej. p→xp \to x y x→px \to p), se forma un ciclo y no existe un ordenamiento válido.

Para calcular SS, obsérvese que como k≤4k \le 4, cada string de consulta tiene a lo sumo 2k≤162^k \le 16 variantes con comodines, obtenidas al reemplazar subconjuntos de posiciones por _. Guardamos un hashmap de string de patrón a índice y buscamos cada variante para recolectar todos los patrones coincidentes de forma eficiente.

Para cada consulta:

  1. Generamos SS enumerando las 2k2^k variantes con comodines.
  2. Si p∉Sp \notin S, inmediatamente imprimimos NO.
  3. En caso contrario, agregamos aristas dirigidas p→xp \to x para todo x∈Sx \in S, x≠px \neq p.

Después de procesar todas las consultas, ejecutamos un orden topológico sobre el grafo de patrones. Si existe un ciclo, imprimimos NO; en caso contrario, imprimimos el orden topológico.

Implementación

Complejidad temporal: O(N+M⋅2K)\mathcal{O}(N + M \cdot 2^K)

#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> adj;
vector<int> color;  // 0 = unvisited, 1 = in current DFS path, 2 = fully processed
vector<int> topo_order;
 
// Returns false if a cycle is detected
bool dfs(int u) {
	color[u] = 1;
	for (int v : adj[u]) {
		if (color[v] == 1) return false;  // back edge = cycle
		if (color[v] == 0) {
			bool no_cycle = dfs(v);
			if (!no_cycle) return false;
		}
	}
 
	color[u] = 2;
	topo_order.push_back(u);
	return true;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m, k;
	cin >> n >> m >> k;
 
	// Map from pattern string to its 0-indexed position in input
	unordered_map<string, int> pat_idx;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		pat_idx[s] = i;
	}
 
	vector<pair<string, int>> queries(m);
	// matches[i] = indices of all patterns that match query i
	vector<vector<int>> matches(m);
 
	for (int i = 0; i < m; i++) {
		cin >> queries[i].first >> queries[i].second;
		queries[i].second--;  // convert to 0-indexed
 
		int req = queries[i].second;
		string query_str = queries[i].first;
 
		// Try all 2^k subsets of positions replaced by '_' to find matching patterns
		for (int mask = 0; mask < (1 << k); mask++) {
			string variant = query_str;
			for (int j = 0; j < k; j++) {
				if (mask >> j & 1) variant[j] = '_';
			}
 
			if (pat_idx.count(variant)) { matches[i].push_back(pat_idx[variant]); }
		}
 
		// The required pattern must itself match the query string
		bool req_found = false;
		for (int x : matches[i]) {
			if (x == req) {
				req_found = true;
				break;
			}
		}
 
		if (!req_found) {
			cout << "NO\n";
			return 0;
		}
	}
 
	// Build the constraint graph: an edge from req -> x means req must appear before x
	adj.assign(n, {});
	color.assign(n, 0);
 
	for (int i = 0; i < m; i++) {
		int req = queries[i].second;
		for (int x : matches[i]) {
			if (x != req) adj[req].push_back(x);
		}
	}
 
	// Topological sort via DFS; cycle means constraints are contradictory
	for (int i = 0; i < n; i++) {
		if (color[i] == 0) {
			bool no_cycle = dfs(i);
			if (!no_cycle) {
				cout << "NO\n";
				return 0;
			}
		}
	}
 
	reverse(topo_order.begin(), topo_order.end());
	cout << "YES\n";
	for (int x : topo_order) cout << x + 1 << " ";
	cout << "\n";
 
	return 0;
}
Fundamentos