Algoritma Boyer-Moore adalah salah satu algoritma pencarian string, dipublikasikan oleh Robert S. Boyer, dan J. Strother Moore pada tahun 1977. Algoritma ini dianggap sebagai algoritma yang paling efisien pada aplikasi umum.Tidak seperti algoritma pencarian string yang ditemukan sebelumnya, algoritma Boyer-Moore mulai mencocokkan karakter dari sebelah kanan pattern. Ide dibalik algoritma ini adalah bahwa dengan memulai pencocokkan karakter dari kanan, dan bukan dari kiri, maka akan lebih banyak informasi yang didapat. (Wikipedia)
Algoritma Boyer-Moore melakukan pencocokan karakter dimulai dari kanan ke kiri. Karakter paling kanan pada pola merupakan karakter pertama yang akan dicocokkan dengan teks. Algoritma ini mempunyai dua fase, yaitu fase preprocessing dan fase pencarian. Pada fase preprocessing terdapat dua buah fungsi untuk menggeser pola ke arah kanan. Kedua fungsi ini disebut good-suffix-shift dan bad-character-shift. Fungsi good-suffix-shift disimpan ke dalam sebuah tabel bmGs berukuran m+1. Sedangkan fungsi bad-character-shift disimpan ke dalam sebuah tabel bmBc yang berukuran n.
Berikut adalah Algoritmanya : (KLIK UNTUK MEMPERBESAR)
0 komentar:
Posting Komentar