Jelaskan Cara kerja dari Algoritma Boyer-Moore

Misalnya ada sebuah usaha pencocokan yang terjadi pada , dan anggap ketidakcocokan pertama terjadi di antara  dan , dengan . Berarti,  dan  tidak sama dengan . Jika  adalah akhiran dari pattern sebelum  dan  adalah sebuah awalan dari pattern, maka penggeseran-penggeseran yang mungkin adalah:

Penggeseran good-suffix yang terdiri dari menyejajarkan potongan  dengan kemunculannya paling kanan di pattern yang didahului oleh karakter yang berbeda dengan . Jika tidak ada potongan seperti itu, maka algoritme akan menyejajarkan akhiran  dari  dengan awalan dari pattern yang sama.

Penggeseran bad-character yang terdiri dari menyejajarkan  dengan kemunculan paling kanan karakter tersebut di pattern. Bila karakter tersebut tidak ada di pattern, maka pattern akan disejajarkan dengan .

Secara sistematis, langkah-langkah yang dilakukan algoritme Boyer-Moore pada saat mencocokkan string adalah:

Algoritme Boyer-Moore mulai mencocokkan pattern pada awal teks.

Dari kanan ke kiri, algoritme ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:

Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).

Semua karakter di pattern cocok. Kemudian algoritme akan memberitahukan penemuan di posisi ini.

Algoritme kemudian menggeser pattern dengan memaksimalkan nilai penggeseran good-suffix dan penggeseran bad-character, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.