Algoritmo de Boyer-Moore
Visual Basic
(3)Publicado el 12 de Agosto del 2005 por Manuel González Rivera
16.055 visualizaciones desde el 12 de Agosto del 2005
El algoritmo de Boyer-Moore es considerado el algoritmo de procesamiento de cadenas (string-matching) más eficiente en las aplicaciones usuales. Una versión simplificada de el o el algoritmo completo es frecuentemente implementada en los editores de texto para los comandos de «búsqueda» y «Reemplazar».
El Algoritmo Boyer-Moore tiene estas características.
- Realiza las comparaciones de derecha a izquierda;
- La fase de preprocesamiento se realiza en O(m+sigma) en tiempo y espacio;
- La fase de búsqueda toma O(mn) en tiempo;
- En el peor caso se necesitan 3n comparaciones de caracteres cuando se busca un patrón no periódico;
- En el mejor caso toma O(n / m).
El Algoritmo Boyer-Moore tiene estas características.
- Realiza las comparaciones de derecha a izquierda;
- La fase de preprocesamiento se realiza en O(m+sigma) en tiempo y espacio;
- La fase de búsqueda toma O(mn) en tiempo;
- En el peor caso se necesitan 3n comparaciones de caracteres cuando se busca un patrón no periódico;
- En el mejor caso toma O(n / m).
41 visualizaciones durante los últimos 90 días