algoritmo di Boyer-Moore

In informatica, l'algoritmo di Boyer-Moore è un algoritmo di confronto fra stringhe efficiente che rappresenta il principale punto di riferimento nel suo ambiente. È stato sviluppato da e nel 1977. L'algoritmo preprocessa la stringa da cercare (il pattern), ma non la stringa esaminata (il testo). È quindi particolarmente adatto per applicazioni in cui il pattern è molto più breve del testo o persiste su più ricerche. L'algoritmo di Boyer–Moore utilizza informazioni raccolte durante la fase di preprocessamento per poter saltare sezioni del testo, risultando in un fattore costante più basso rispetto a molti altri algoritmi su stringhe. In generale, l'algoritmo è eseguito più velocemente con l'aumentare della lunghezza del pattern. La caratteristica fondamentale dell'algoritmo è il confronto in coda del pattern piuttosto che in testa, e la possibilità di muoversi lungo il testo saltando interi gruppi di caratteri piuttosto che verificare ogni singolo carattere presente nel testo.