Estructura y Gestión de Memoria

Al implementar estructuras de datos como el Trie mediante arreglos estáticos en C++, es fundamental considerar el ámbito de inicialización. Si los arreglos se declaran globalmente (fuera de la clase), se recomienda utilizar memset dentro de la función principal o el cosntructor para limpiar residuos de ejecuciones previas. Si se declaran como miembros de la clase, la inicialización puede gestionarse directamente en el constructor.

1. Implementación Básica de un Trie

Un Trie es una estructura de árbol eficiente para recuperar llaves en un conjunto de cadenas. Cada nodo representa un carácter y los caminos desde la raíz forman los prefijos.

class PrefijoTrie {
private:
    int transiciones[100005][26];
    int finales[100005];
    int contador_nodos;

public:
    PrefijoTrie() {
        memset(transiciones, 0, sizeof(transiciones));
        memset(finales, 0, sizeof(finales));
        contador_nodos = 0;
    }
    
    void insertar(string palabra) {
        int actual = 0;
        for (char c : palabra) {
            int idx = c - 'a';
            if (!transiciones[actual][idx]) {
                transiciones[actual][idx] = ++contador_nodos;
            }
            actual = transiciones[actual][idx];
        }
        finales[actual]++;
    }
    
    bool buscar(string palabra) {
        int actual = 0;
        for (char c : palabra) {
            int idx = c - 'a';
            if (!transiciones[actual][idx]) return false;
            actual = transiciones[actual][idx];
        }
        return finales[actual] > 0;
    }
    
    bool empiezaCon(string prefijo) {
        int actual = 0;
        for (char c : prefijo) {
            int idx = c - 'a';
            if (!transiciones[actual][idx]) return false;
            actual = transiciones[actual][idx];
        }
        return true;
    }
};

2. Sustitución de Palabras mediante Raíces

En este escenario, se busca reducir palabras a su raíz más corta preesnte en un diccionario. El Trie permite una búsqueda incremental que se detiene en el primer nodo marcado como final.

class BuscadorRaices {
public:
    int matriz[100010][26], marca[100010], n_idx = 0;

    void agregar(string s) {
        int p = 0;
        for (char c : s) {
            int u = c - 'a';
            if (!matriz[p][u]) matriz[p][u] = ++n_idx;
            p = matriz[p][u];
        }
        marca[p]++;
    }

    string obtenerPrefijo(string s) {
        string temp = "";
        int p = 0;
        for (char c : s) {
            int u = c - 'a';
            if (!matriz[p][u]) break;
            temp += c;
            p = matriz[p][u];
            if (marca[p]) return temp;
        }
        return "";
    }

    string replaceWords(vector<string>& dictionary, string sentence) {
        n_idx = 0;
        memset(matriz, 0, sizeof(matriz));
        memset(marca, 0, sizeof(marca));
        for (auto& s : dictionary) agregar(s);

        stringstream ss(sentence);
        string palabra, resultado = "";
        while (ss >> palabra) {
            string pref = obtenerPrefijo(palabra);
            resultado += (pref != "" ? pref : palabra) + " ";
        }
        if (!resultado.empty()) resultado.pop_back();
        return resultado;
    }
};

3. Diccionario Mágico con Búsqueda Difusa

Este problema requiere determinar si una palabra existe en el diccionario tras cambiar exactamente un carácter. Se utiliza DFS sobre el Trie para explorar las ramas permitiendo un error.

class DiccionarioMagico {
    int trie[10001][26], es_fin[10001], nodos = 0;
public:
    DiccionarioMagico() {
        memset(trie, 0, sizeof trie);
        memset(es_fin, 0, sizeof es_fin);
        nodos = 0;
    }
    
    void buildDict(vector<string> dictionary) {
        for (string& s : dictionary) {
            int p = 0;
            for (char c : s) {
                int v = c - 'a';
                if (!trie[p][v]) trie[p][v] = ++nodos;
                p = trie[p][v];
            }
            es_fin[p] = 1;
        }
    }
    
    bool exploracion(string& s, int p, int idx, int fallos) {
        if (idx == s.size()) return fallos == 1 && es_fin[p];
        
        for (int i = 0; i < 26; i++) {
            if (!trie[p][i]) continue;
            int nuevos_fallos = fallos + (s[idx] - 'a' != i);
            if (nuevos_fallos <= 1) {
                if (exploracion(s, trie[p][i], idx + 1, nuevos_fallos)) return true;
            }
        }
        return false;
    }

    bool search(string searchWord) {
        return exploracion(searchWord, 0, 0, 0);
    }
};

4. Codificación de Longitud Mínima

Para encontrar la longitud mínima de una codificación donde las palabras que son sufijos de otras se omiten, insertamos las palabrsa invertidas en el Trie. Los nodos hoja representarán las palabras que no son sufijos de ninguna otra.

class CodificadorSufijos {
    int nodos[15000][26], hijos[15000], prof[15000], total_nodos = 0;
public:
    void insertarInvertida(string s) {
        reverse(s.begin(), s.end());
        int p = 0;
        for (char c : s) {
            int v = c - 'a';
            if (!nodos[p][v]) nodos[p][v] = ++total_nodos;
            hijos[p]++;
            p = nodos[p][v];
        }
        prof[p] = s.size();
    }

    int minimumLengthEncoding(vector<string>& words) {
        memset(nodos, 0, sizeof nodos);
        memset(hijos, 0, sizeof hijos);
        total_nodos = 0;
        for (string& w : words) insertarInvertida(w);
        
        int acumulado = 0;
        for (int i = 1; i <= total_nodos; i++) {
            if (hijos[i] == 0) acumulado += prof[i] + 1;
        }
        return acumulado;
    }
};

5. Suma de Pares en un Mapa de Prefijos

Esta variante asocia un valor numérico a cada cadena. Al consultar un prefijo, se debe retornar la suma de los valores de todas las llaves que comienzan con dicho prefijo.

class MapaSuma {
    int hijos[2600][26], valores[2600], n_cnt = 0;
public:
    MapSum() {
        memset(hijos, 0, sizeof hijos);
        memset(valores, 0, sizeof valores);
        n_cnt = 0;
    }
    
    void insert(string key, int val) {
        int p = 0;
        for (char c : key) {
            int v = c - 'a';
            if (!hijos[p][v]) hijos[p][v] = ++n_cnt;
            p = hijos[p][v];
        }
        valores[p] = val;
    }
    
    int calcularSubarbol(int p) {
        int s = valores[p];
        for (int i = 0; i < 26; i++) {
            if (hijos[p][i]) s += calcularSubarbol(hijos[p][i]);
        }
        return s;
    }

    int sum(string prefix) {
        int p = 0;
        for (char c : prefix) {
            int v = c - 'a';
            if (!hijos[p][v]) return 0;
            p = hijos[p][v];
        }
        return calcularSubarbol(p);
    }
};

6. Máximo XOR mediante Trie Binario

Para encontrar el máximo valor XOR entre dos números en un conjunto, se utiliza un Trie binario para almacenar la representación de 31 bits de cada número. En la búsqueda, intentamos elegir siempre el bit opuesto al del número actual para maximizar el resultado.

class MaxXOR {
    int arbol_bits[800001][2], nodos_idx = 0;
public:
    void insertarBinario(int n) {
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (!arbol_bits[p][bit]) arbol_bits[p][bit] = ++nodos_idx;
            p = arbol_bits[p][bit];
        }
    }

    int buscarMaximo(int n) {
        int p = 0, local_max = 0;
        for (int i = 30; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (arbol_bits[p][!bit]) {
                local_max = (local_max << 1) | 1;
                p = arbol_bits[p][!bit];
            } else {
                local_max = (local_max << 1) | 0;
                p = arbol_bits[p][bit];
            }
        }
        return local_max;
    }

    int findMaximumXOR(vector<int>& nums) {
        memset(arbol_bits, 0, sizeof arbol_bits);
        nodos_idx = 0;
        for (int x : nums) insertarBinario(x);
        int max_global = 0;
        for (int x : nums) max_global = max(max_global, buscarMaximo(x));
        return max_global;
    }
};