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: lista de strings (patrones a buscar)
• text: string donde buscar

Salida

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

Ejemplo

aho_corasick(["he", "she", "his", "hers"], "ushers")
# => [["she", 1], ["he", 2], ["hers", 2]]

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

Restricciones

• 1 <= len(patterns) <= 100
• 1 <= len(patterns[i]) <= 100
• 1 <= len(text) <= 10,000
• Los patrones pueden repetirse en la lista; trátalos de forma independiente
• Los caracteres son ASCII minúsculas