Algoritmo Aho-Corasick

Implementa el algoritmo Aho-Corasick para búsqueda simultánea de múltiples patrones en un texto.

Dado un array de patrones y un texto, construye un autómata finito determinista (trie + enlaces de fallo) y recorre el texto una sola vez para encontrar todas las ocurrencias de todos los patrones.

Complejidad esperada

• Construcción del autómata: O(Σ patrones)
• Búsqueda: O(n + z) donde n es la longitud del texto y z el número de coincidencias

Entrada

• patterns: array de strings (patrones a buscar)
• text: string donde buscar

Salida

Array de pares [patrón, índice] con todas las ocurrencias encontradas, ordenado por índice de inicio ascendente y luego por patrón lexicográfico ascendente.

Ejemplo

ahoCorasick(["he", "she", "his", "hers"], "ushers")
// => [["she", 1], ["he", 2], ["hers", 2]]

ahoCorasick(["a", "aa", "aaa"], "aaaa")
// => [["a",0],["aa",0],["aaa",0],["a",1],["aa",1],["aaa",1],["a",2],["aa",2],["a",3]]

Restricciones

• 1 <= patterns.length <= 100
• 1 <= patterns[i].length <= 100
• 1 <= text.length <= 10,000
• Los patrones pueden repetirse en el array; trátalos de forma independiente
• Los caracteres son ASCII minúsculas