Búsqueda ingenua y KMP

Encuentra un patrón en un texto sin retroceder nunca el puntero del texto. Velocidad a partir de una tabla de fallo precalculada.

Un mismatch es información

• Búsqueda ingenua: ante un mismatch, desliza 1 y relee → O(n·m)
• Los caracteres coincididos son un prefijo conocido del patrón
• Si ese prefijo se traslapa con su propio sufijo, desliza más de 1
• El puntero del texto nunca rebobina → O(n+m)

La función de fallo

• lps[i] = prefijo propio más largo de pattern[:i+1] que también es sufijo
• Se construye en O(m) comparando el patrón contra SÍ MISMO
• Ante un mismatch tras j coincidencias → reanuda como si hubieran coincidido lps[j−1]
• lps("ababc") = [0,0,1,2,0]

Mira deslizarse al patrón

Azul = comparando · verde = coincidió · rojo = mismatch. Después de que abab falla, el patrón brinca hacia adelante — sin rebobinar.

Lineal vs cuadrático

aaaa…a vs aaaa…b: ingenuo 398K comparaciones, KMP 16K → 25× menos.

Para llevar

El ingenuo no está mal — está frágil (cuadrático latente con entrada repetitiva). KMP paga un setup O(m) por una garantía lineal, sea cual sea la entrada. Sigue: Rabin-Karp — comparar números (rolling hash), no cadenas.