Arrays y árboles de sufijos
Indexa el TEXTO una vez; luego encuentra cualquier patrón en O(m log n).
Un suffix array = el orden ordenado de todos los sufijos del texto.
Por qué funciona ordenar los sufijos
- Toda subcadena es el prefijo de algún sufijo
- Ordena los sufijos → las ocurrencias de un patrón forman un bloque CONTIGUO
- Dos búsquedas binarias acotan el bloque: O(m log n) por consulta
- Guarda solo n índices de inicio, no los sufijos → espacio O(n)
Mira la búsqueda binaria sobre sufijos
Sufijos ordenados de 'banana'; búsqueda de 'ana'.
Naranja = punto medio comparado · bloque encontrado = posiciones [1, 3].
El índice se amortiza entre consultas
El build cuesta 12ms por adelantado; cada consulta es minúscula. El rescaneo relee el texto cada vez. Cruce ≈ 50 consultas.
Prefix doubling + LCP
- Build: rankea por los primeros 1, luego 2, 4, … chars, reutilizando los ranks previos → O(n log²n)
- Array LCP (Kasai, O(n)): prefijo común más largo de sufijos ordenados adyacentes
- Subcadena repetida más larga = max(LCP); subcadena común más larga; conteo de distintas
- Suffix array + LCP = un árbol de sufijos a ¼ de la memoria (4n vs ~20n bytes)
Conclusión
Indexar: paga un build fijo para que las consultas repetidas salgan baratas — vale la pena pasando el cruce.
Genómica (FM-index), búsqueda full-text y compresión BWT viven aquí.
Siguiente: Aho-Corasick — un autómata para miles de patrones.