La búsqueda de patrones es un problema importante en informática. Cuando buscamos una string en un bloc de notas/archivo de Word, navegador o base de datos, se utilizan algoritmos de búsqueda de patrones para mostrar los resultados de la búsqueda. Un enunciado de problema típico sería:
Dado un texto txt[0..n-1] y un patrón pat[0..m-1] donde n es la longitud del texto y m es la longitud del patrón, escriba un función search(char pat[], char txt[]) que imprime todas las apariciones de pat[] en txt[]. Puede suponer que n > m.
Ejemplos:
Input: txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: Pattern found at index 10
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
En esta publicación, discutiremos el algoritmo de búsqueda de patrones de Boyer Moore. Al igual que los algoritmos KMP y Finite Automata , el algoritmo de Boyer Moore también preprocesa el patrón.
Boyer Moore es una combinación de los dos enfoques siguientes.
- Heurística de mal carácter
- Buen sufijo heurístico
Las dos heurísticas anteriores también se pueden usar de forma independiente para buscar un patrón en un texto. Primero comprendamos cómo dos enfoques independientes funcionan juntos en el algoritmo de Boyer Moore. Si echamos un vistazo al algoritmo Naive , desliza el patrón sobre el texto uno a uno. El algoritmo KMP realiza un preprocesamiento sobre el patrón para que el patrón pueda cambiarse en más de uno. El algoritmo de Boyer Moore realiza preprocesamiento por la misma razón. Procesa el patrón y crea diferentes arrays para cada una de las dos heurísticas. En cada paso, desliza el patrón por el máximo de las diapositivas sugeridas por cada una de las dos heurísticas. Por lo tanto, utiliza la mayor compensación sugerida por las dos heurísticas en cada paso .
A diferencia de los algoritmos de búsqueda de patrones anteriores, el algoritmo de Boyer Moore comienza a buscar coincidencias desde el último carácter del patrón.
En esta publicación, discutiremos la heurística del mal carácter y la heurística del buen sufijo en la próxima publicación.
Heurística de mal carácter
La idea de la heurística del mal carácter es simple. El carácter del texto que no coincide con el carácter actual del patrón se denomina carácter incorrecto . En caso de desajuste, cambiamos el patrón hasta que:
- el desajuste se convierte en un partido
- El patrón P se mueve más allá del carácter no coincidente.
Caso 1: la discrepancia se convierte en coincidencia
Buscaremos la posición de la última aparición del carácter no coincidente en el patrón y, si el carácter no coincidente existe en el patrón, cambiaremos el patrón para que se alinee con el carácter no coincidente en el texto t
caso 1
Explicación: En el ejemplo anterior, obtuvimos una discrepancia en la posición 3. Aquí nuestro carácter de discrepancia es «A». Ahora buscaremos la última aparición de «A» en el patrón. Obtuvimos «A» en la posición 1 en el patrón (mostrado en azul) y esta es la última vez que aparece. Ahora cambiaremos el patrón 2 veces para que la «A» del patrón se alinee con la «A» del texto.
Caso 2: el patrón se mueve más allá del carácter que no coincide
. Buscaremos la posición de la última aparición del carácter que no coincide en el patrón y, si el carácter no existe, cambiaremos el patrón más allá del carácter que no coincide.
caso2
Explicación:
Aquí tenemos una discrepancia en la posición 7. El carácter «C» que no coincide no existe en el patrón antes de la posición 7, por lo que cambiaremos el patrón a la posición 7 y finalmente, en el ejemplo anterior, obtendremos una combinación perfecta de patrón (que se muestra en Verde). Estamos haciendo esto porque «C» no existe en el patrón, por lo que en cada cambio antes de la posición 7 obtendremos una discrepancia y nuestra búsqueda será infructuosa.
En la siguiente implementación, preprocesamos el patrón y almacenamos la última aparición de cada carácter posible en una array de tamaño igual al tamaño del alfabeto. Si el carácter no está presente en absoluto, puede resultar en un cambio de m (longitud del patrón). Por lo tanto, la heurística del mal carácter toma 
tiempo en el mejor de los casos.
C++
/* C++ Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
// The preprocessing function for Boyer Moore's
// bad character heuristic
void badCharHeuristic( string str, int size,
int badchar[NO_OF_CHARS])
{
int i;
// Initialize all occurrences as -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence
// of a character
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
/* Fill the bad character array by calling
the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with
// respect to text
while(s <= (n - m))
{
int j = m - 1;
/* Keep reducing index j of pattern while
characters of pattern and text are
matching at this shift s */
while(j >= 0 && pat[j] == txt[s + j])
j--;
/* If the pattern is present at current
shift, then index j will become -1 after
the above loop */
if (j < 0)
{
cout << "pattern occurs at shift = " << s << endl;
/* Shift the pattern so that the next
character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s + j]]);
}
}
/* Driver code */
int main()
{
string txt= "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}
// This code is contributed by rathbhupendra
C
/* C Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
# include <limits.h>
# include <string.h>
# include <stdio.h>
# define NO_OF_CHARS 256
// A utility function to get maximum of two integers
int max (int a, int b) { return (a > b)? a: b; }
// The preprocessing function for Boyer Moore's
// bad character heuristic
void badCharHeuristic( char *str, int size,
int badchar[NO_OF_CHARS])
{
int i;
// Initialize all occurrences as -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence
// of a character
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
void search( char *txt, char *pat)
{
int m = strlen(pat);
int n = strlen(txt);
int badchar[NO_OF_CHARS];
/* Fill the bad character array by calling
the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with
// respect to text
while(s <= (n - m))
{
int j = m-1;
/* Keep reducing index j of pattern while
characters of pattern and text are
matching at this shift s */
while(j >= 0 && pat[j] == txt[s+j])
j--;
/* If the pattern is present at current
shift, then index j will become -1 after
the above loop */
if (j < 0)
{
printf("\n pattern occurs at shift = %d", s);
/* Shift the pattern so that the next
character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
s += (s+m < n)? m-badchar[txt[s+m]] : 1;
}
else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s+j]]);
}
}
/* Driver program to test above function */
int main()
{
char txt[] = "ABAAABCD";
char pat[] = "ABC";
search(txt, pat);
return 0;
}
Java
/* Java Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
class AWQ{
static int NO_OF_CHARS = 256;
//A utility function to get maximum of two integers
static int max (int a, int b) { return (a > b)? a: b; }
//The preprocessing function for Boyer Moore's
//bad character heuristic
static void badCharHeuristic( char []str, int size,int badchar[])
{
// Initialize all occurrences as -1
for (int i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence
// of a character (indices of table are ascii and values are index of occurrence)
for (int i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
static void search( char txt[], char pat[])
{
int m = pat.length;
int n = txt.length;
int badchar[] = new int[NO_OF_CHARS];
/* Fill the bad character array by calling
the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with
// respect to text
//there are n-m+1 potential alignments
while(s <= (n - m))
{
int j = m-1;
/* Keep reducing index j of pattern while
characters of pattern and text are
matching at this shift s */
while(j >= 0 && pat[j] == txt[s+j])
j--;
/* If the pattern is present at current
shift, then index j will become -1 after
the above loop */
if (j < 0)
{
System.out.println("Patterns occur at shift = " + s);
/* Shift the pattern so that the next
character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
//txt[s+m] is character after the pattern in text
s += (s+m < n)? m-badchar[txt[s+m]] : 1;
}
else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s+j]]);
}
}
/* Driver program to test above function */
public static void main(String []args) {
char txt[] = "ABAAABCD".toCharArray();
char pat[] = "ABC".toCharArray();
search(txt, pat);
}
}
Python3
# Python3 Program for Bad Character Heuristic
# of Boyer Moore String Matching Algorithm
NO_OF_CHARS = 256
def badCharHeuristic(string, size):
'''
The preprocessing function for
Boyer Moore's bad character heuristic
'''
# Initialize all occurrence as -1
badChar = [-1]*NO_OF_CHARS
# Fill the actual value of last occurrence
for i in range(size):
badChar[ord(string[i])] = i;
# return initialized list
return badChar
def search(txt, pat):
'''
A pattern searching function that uses Bad Character
Heuristic of Boyer Moore Algorithm
'''
m = len(pat)
n = len(txt)
# create the bad character list by calling
# the preprocessing function badCharHeuristic()
# for given pattern
badChar = badCharHeuristic(pat, m)
# s is shift of the pattern with respect to text
s = 0
while(s <= n-m):
j = m-1
# Keep reducing index j of pattern while
# characters of pattern and text are matching
# at this shift s
while j>=0 and pat[j] == txt[s+j]:
j -= 1
# If the pattern is present at current shift,
# then index j will become -1 after the above loop
if j<0:
print("Pattern occur at shift = {}".format(s))
'''
Shift the pattern so that the next character in text
aligns with the last occurrence of it in pattern.
The condition s+m < n is necessary for the case when
pattern occurs at the end of text
'''
s += (m-badChar[ord(txt[s+m])] if s+m<n else 1)
else:
'''
Shift the pattern so that the bad character in text
aligns with the last occurrence of it in pattern. The
max function is used to make sure that we get a positive
shift. We may get a negative shift if the last occurrence
of bad character in pattern is on the right side of the
current character.
'''
s += max(1, j-badChar[ord(txt[s+j])])
# Driver program to test above function
def main():
txt = "ABAAABCD"
pat = "ABC"
search(txt, pat)
if __name__ == '__main__':
main()
# This code is contributed by Atul Kumar
# (www.facebook.com/atul.kr.007)
C#
/* C# Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
using System;
public class AWQ{
static int NO_OF_CHARS = 256;
//A utility function to get maximum of two integers
static int max (int a, int b) { return (a > b)? a: b; }
//The preprocessing function for Boyer Moore's
//bad character heuristic
static void badCharHeuristic( char []str, int size,int []badchar)
{
int i;
// Initialize all occurrences as -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence
// of a character
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
static void search( char []txt, char []pat)
{
int m = pat.Length;
int n = txt.Length;
int []badchar = new int[NO_OF_CHARS];
/* Fill the bad character array by calling
the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with
// respect to text
while(s <= (n - m))
{
int j = m-1;
/* Keep reducing index j of pattern while
characters of pattern and text are
matching at this shift s */
while(j >= 0 && pat[j] == txt[s+j])
j--;
/* If the pattern is present at current
shift, then index j will become -1 after
the above loop */
if (j < 0)
{
Console.WriteLine("Patterns occur at shift = " + s);
/* Shift the pattern so that the next
character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
s += (s+m < n)? m-badchar[txt[s+m]] : 1;
}
else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s+j]]);
}
}
/* Driver program to test above function */
public static void Main() {
char []txt = "ABAAABCD".ToCharArray();
char []pat = "ABC".ToCharArray();
search(txt, pat);
}
}
// This code is contributed by PrinciRaj19992
Javascript
<script>
/* Javascript Program for Bad Character Heuristic of Boyer
Moore String Matching Algorithm */
let NO_OF_CHARS = 256;
// A utility function to get maximum of two integers
function max (a,b)
{
return (a > b)? a: b;
}
// The preprocessing function for Boyer Moore's
// bad character heuristic
function badCharHeuristic(str,size,badchar)
{
// Initialize all occurrences as -1
for (let i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence
// of a character (indices of table are ascii and values are index of occurrence)
for (i = 0; i < size; i++)
badchar[ str[i].charCodeAt(0)] = i;
}
/* A pattern searching function that uses Bad
Character Heuristic of Boyer Moore Algorithm */
function search(txt,pat)
{
let m = pat.length;
let n = txt.length;
let badchar = new Array(NO_OF_CHARS);
/* Fill the bad character array by calling
the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);
let s = 0; // s is shift of the pattern with
// respect to text
// there are n-m+1 potential alignments
while(s <= (n - m))
{
let j = m-1;
/* Keep reducing index j of pattern while
characters of pattern and text are
matching at this shift s */
while(j >= 0 && pat[j] == txt[s+j])
j--;
/* If the pattern is present at current
shift, then index j will become -1 after
the above loop */
if (j < 0)
{
document.write("Patterns occur at shift = " + s);
/* Shift the pattern so that the next
character in text aligns with the last
occurrence of it in pattern.
The condition s+m < n is necessary for
the case when pattern occurs at the end
of text */
//txt[s+m] is character after the pattern in text
s += (s+m < n)? m-badchar[txt[s+m].charCodeAt(0)] : 1;
}
else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s+j].charCodeAt(0)]);
}
}
/* Driver program to test above function */
let txt="ABAAABCD".split("");
let pat = "ABC".split("");
search(txt, pat);
// This code is contributed by unknown2108
</script>
pattern occurs at shift = 4
Complejidad de tiempo: O (nxm)
Espacio Auxiliar: O(1)
La heurística del mal carácter puede tomar 
tiempo en el peor de los casos. El peor caso ocurre cuando todos los caracteres del texto y el patrón son iguales. Por ejemplo, txt[] = “AAAAAAAAAAAAAAAAAA” y pat[] = “AAAAA”. La Heurística de Carácter Malo puede tomar O(n/m) en el mejor de los casos. El mejor caso ocurre cuando todos los caracteres del texto y el patrón son diferentes.
Algoritmo de Boyer-Moore | Buen sufijo heurístico
Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA