Gostaria de saber como funciona o algoritmo de busca de texto de Boyer-Moore com a regra de Galil. Tentei procurar, mas não consegui entender as informações que encontrei, por exemplo, esta página da Wikipedia . E por que com essa regra vamos para uma complexidade de tempo linear?
7
Respostas:
O algoritmo é baseado em um princípio simples. Suponha que estamos tentando corresponder a uma substring de comprimento n . Vamos ver primeiro o caractere no índice m. Se esse caractere não estiver na sequência, sabemos que a substring desejada não pode ser iniciada nos caracteres nos índices 1 2 .... n
Se esse caractere estiver em nossa string, assumiremos que é o último lugar da string que ele pode estar. Iremos então voltar e começar a tentar combinar a corda a partir desse possível local de partida. Esta informação é minha primeira mesa.
Depois de começar a corresponder a partir do início da substring, quando encontro uma incompatibilidade, não posso simplesmente começar do zero. Eu poderia estar parcialmente em uma partida começando em um ponto diferente. Por exemplo, se estou tentando corresponder anand em ananand corresponder com sucesso, anan, perceba que o seguinte a não é um anúncio, mas apenas correspondi a um e, portanto, devo voltar a tentar corresponder meu terceiro caractere na minha substring . Essas informações "Se eu falhar após corresponder x caracteres, eu poderia estar no y-ésimo caractere de uma correspondência" são armazenadas na segunda tabela.
Observe que, quando não consigo corresponder, a segunda tabela sabe quanto tempo em uma correspondência posso basear-me no que acabei de corresponder. A primeira tabela sabe a que distância eu poderia estar baseado no personagem que acabei de ver que não correspondia. Você deseja usar o mais pessimista dessas duas informações.
fonte