Aho-Corasick: búsqueda multi-patrón

Encuentra miles de patrones en UNA pasada. KMP con un trie. El costo de búsqueda no depende de cuántos patrones sean.

Tres capas

• Trie: todos los patrones en un árbol de prefijos (prefijos comunes compartidos)
• Failure links: el "dónde retomar" de KMP generalizado al árbol
• Output links: una posición reporta cada patrón que termina ahí
• Pasa el texto una vez; el puntero nunca rebobina → O(n + matches)

Mira al autómata escanear

Diccionario {he, she, his, hers}, texto 'ushers'. ◆ = aquí termina un patrón. 'she' dispara she + he (output link); 'r' sigue un failure link hasta 'her'.

Una pasada vs k pasadas

Aho-Corasick: plana (una pasada, sin importar cuántos patrones). 500 patrones → 260× menos caracteres examinados.

Dos cosas que hay que hacer bien

• Fusiona los OUTPUT links a lo largo de los fallos, o se te escapa 'he' dentro de 'she'
• Construye los failure links por anchura (primero los superficiales) — la dependencia de orden de KMP
• Conjunto fijo de patrones → si cambian los patrones, hay que reconstruir
• ¿Un solo patrón? Mejor usa KMP/Boyer-Moore

Para llevar

El tema del bloque: precalcula ESTRUCTURA antes del escaneo para abaratar el matching. Tabla de KMP · rolling hash · tabla de saltos · índice de sufijos · este autómata — todos la misma jugada. Bloque de cadenas terminado. Siguiente bloque: los paradigmas detrás de los algoritmos.