O algoritmo de Boyer-Moore é considerado o algoritmo de correspondência de string mais eficiente em aplicativos comuns, como, por exemplo, editores...

O algoritmo de Boyer-Moore é considerado o algoritmo de correspondência de string mais eficiente em aplicativos comuns, como, por exemplo, editores de texto e substituições de comandos. O motivo é que ele é o mais rápido quando o alfabeto é de tamanho moderado e o padrão é relativamente longo. Um problema típico seria: dado um texto txt[0, ..., n-1] e um padrão pat[0, ..., m-1], escrever uma função de pesquisa(char pat [], char txt []) que imprima todas as ocorrências de pat[] no txt[], assumindo que n> m.

Exemplo:

​​​​​​​Entrada: txt[]= "Este é um texto de teste."

pat[]="teste"

Saída: Padrão encontrado no índice 19.

Qual é o pior caso de tempo de execução na fase de pesquisa do algoritmo de Boyer-Moore?

A. 

O(n).

B. 

O(mn).

C. 

O(n log n).

D. 

O(log n).

E. 

O(m+n).