¿Quieres saber qué significa bm?
El algoritmo BM se considera un algoritmo de coincidencia de cadenas sublineal. En el peor de los casos, la complejidad temporal de encontrar todos los patrones es O (Mn) y, en el mejor de los casos, la complejidad temporal de encontrar todos los patrones haciendo coincidir es O (n/m).
La idea principal del algoritmo BM se describe a continuación:
El orden coincidente de las cadenas de patrones es de derecha a izquierda.
1. Primero alinee p y t, es decir, alinee p y t.
2. Luego, la coincidencia comienza desde el carácter más a la derecha de la cadena de patrón P, es decir, se juzga si P [m] y t [m] coinciden.
Si la coincidencia tiene éxito, muévase hacia la izquierda para determinar si p[m-1] y t[m-1] coinciden, y así sucesivamente, si la coincidencia no tiene éxito, se realiza el deslizamiento de cadenas.
El principio del algoritmo BM:
A diferencia de la comparación carácter por carácter en la búsqueda de fuerza bruta, Boyer-Moore aprovecha al máximo la información del preprocesamiento de P para omitir tantos caracteres como sea posible. lo más posible. Normalmente, comenzamos comparando una cadena desde la primera letra y procedemos una por una. Una vez que descubras diferentes personajes, deberás comenzar desde cero para la siguiente comparación.
De esta manera, debes comparar todos los caracteres de la cadena uno por uno. La clave del algoritmo de Boyer-Moore es que al comparar el último carácter de P, podemos decidir omitir uno o más caracteres. Si el último carácter no coincide, no es necesario seguir comparando el carácter anterior.
Si el último carácter no aparece en p, entonces podemos omitir directamente n caracteres de t y comparar los siguientes n caracteres, donde n es la longitud de p (ver definición).
Si el último carácter aparece en P, debe contar el número de caracteres omitidos (es decir, todo el P retrocede) y luego continuar con los pasos anteriores para comparar. Esta forma de mover personajes, en lugar de compararlos uno por uno, es la clave para que el algoritmo sea tan eficiente.