Apenas estendendo o comentário anterior:
a) Força bruta sempre é o pior desempenho e não usa hash. Sua complexidade no pior caso é de O(nm).
b) Knuth-Pratt-Morris tem um algorítmo dividido em duas porções, com complexidades respectivas O(n) e O (k) e a complexidade do algorítmo é O (n+k). No pior caso aproxima-se à força-bruta O(mn)
c) Knuth-Pratt-Morris não faz comparações da direita para a esquerda e sim da esquerda para a direita. Boyer-Moore é que faz comparações da direita para a esquerda;
d) A complexidade do Rabin-Karp é, em média, de O(n+m) a O(nm). No pior caso é de O( (n – m +1)m ), praticamente o mesmo caso de Boyer-Moore para o pior caso. e) Boyer-Moore utiliza heurísticas conhecidas como a “heurística-do-bom- sufixo” e a “heurística-do-mau-caractere”. (CORRETO)
A abordagem de Boyer-Moore é tentar combinar o último caractere do padrão em vez do primeiro com a suposição de que, se não houver correspondência no final, não é necessário tentar combinar no início. Isso permite "grandes saltos", portanto o BM funciona melhor quando o padrão e o texto que você procura são semelhantes a "texto natural" (isto é, inglês)
Knuth-Morris-Pratt procura as ocorrências de uma "palavra" W dentro de uma "string de texto" principal, empregando a observação de que, quando ocorre uma falta de correspondência, a própria palavra incorpora informações suficientes para determinar onde a próxima partida poderia começar, ignorando assim a re-examinação de caracteres anteriormente correspondentes. (Fonte: Wiki)
Isso significa que o KMP é mais adequado para conjuntos pequenos como o DNA (ACTG)
https://pt.stackoverflow.com/questions/231105/qual-%C3%A9-a-diferen%C3%A7a-principal-entre-os-algoritmos-knuth-morris-pratt-e-boyer-moor