Semanas 19 y 20 Tries y Cadenas

Semanas 19 y 20: Tries y Cadenas

Construir la base de tries para resolver búsquedas por prefijo, diccionarios con comodines y reemplazo de palabras por raíces.

Problema	Patrón	API
Implement Trie	Trie básico	`Trie`
Design Add and Search Words Data Structure	Trie + DFS con comodín	`WordDictionary`
Replace Words	Trie + prefijo más corto	`replace_words`
Word Search II	Trie + backtracking en matriz	`find_words`
KMP Pattern Search	KMP	`find_pattern_positions`
Rabin-Karp Pattern Search	Rolling hash + verificación	`rabin_karp_positions`
Z Function	Prefijos compartidos por posición	`z_function`
Multi-pattern Search	Aho-Corasick	`find_multi_pattern_positions`
Find All Anagrams in a String	Ventana + frecuencias	`find_anagram_starts`
Repeated Substring Pattern	KMP conceptual / string doubling	`repeated_substring_pattern`
Longest Common Prefix	Comparación incremental de prefijos	`longest_common_prefix`
Longest Duplicate Substring	Búsqueda binaria + ventanas repetidas	`longest_duplicate_substring`
Longest Palindromic Substring	Expansión por centros	`longest_palindromic_substring`
Count Palindromic Substrings	Expansión por centros	`count_palindromic_substrings`
Shortest Palindrome	KMP sobre texto y reverso	`shortest_palindrome`

Cada arista representa un carácter.
is_word separa "este prefijo existe" de "esta palabra existe".
Un comodín . se resuelve probando todos los hijos posibles en ese nivel.
Para reemplazar palabras, conviene devolver la primera raíz completa encontrada durante el recorrido.
Word Search II combina trie con DFS en cuatro direcciones y marca temporalmente cada celda visitada para no reutilizarla dentro de la misma palabra.
KMP evita retroceder en el texto usando una tabla de prefijos del patrón.
Rabin-Karp usa rolling hash para filtrar ventanas candidatas y compara bytes para evitar falsos positivos por colisión.
La Z-function calcula cuánto coincide cada sufijo con el prefijo del texto.
Aho-Corasick comparte prefijos entre patrones y usa enlaces de fallo para continuar la búsqueda sin reiniciar el texto.
Una ventana de anagramas mantiene conteos y mueve un carácter de entrada por uno de salida.
Longest Common Prefix reduce el prefijo candidato contra cada palabra hasta que deja de coincidir.
Longest Duplicate Substring puede buscar la longitud máxima con búsqueda binaria y verificar duplicados con ventanas.
La expansión por centros trata palíndromos impares y pares con la misma idea: crecer mientras los extremos coinciden.
Shortest Palindrome puede verse como buscar el prefijo palindrómico más largo y anteponer el reverso del sufijo restante.

Operación	Tiempo	Espacio
Insertar palabra	`O(L)`	`O(L)` en nuevos nodos
Buscar palabra exacta	`O(L)`	`O(1)` adicional
Buscar prefijo	`O(P)`	`O(1)` adicional
Buscar con comodines	`O(26^W * L)` en peor caso	`O(L)` por recursión
Reemplazar oración	`O(total de caracteres)`	`O(total del diccionario)`
Word Search II	`O(m * n * 4^L)` peor caso	`O(total del diccionario + L)`
KMP	`O(n + m)`	`O(m)`
Rabin-Karp	`O(n + m)` promedio con verificación	`O(1)`
Z Function	`O(n)`	`O(n)`
Aho-Corasick	`O(n + total de patrones + coincidencias)`	`O(total de patrones)`
Anagramas en ventana	`O(n + m)`	`O(1)` para alfabeto fijo
Patrón repetido	`O(n)` promedio por búsqueda interna	`O(n)`
Longest Common Prefix	`O(total de caracteres comparados)`	`O(p)`
Longest Duplicate Substring	`O(n^2 log n)` peor caso	`O(n)`
Longest Palindromic Substring	`O(n^2)`	`O(n)`
Count Palindromic Substrings	`O(n^2)`	`O(n)`
Shortest Palindrome	`O(n)`	`O(n)`

Continuar el hito 190 con grafos y Union-Find como siguiente bloque de contenido del repositorio.