dalam puzzle yang tersusun secara random • Penelitian sebelumnya – Algoritma Knuth-Morris-Pratt (word search puzzle) – Perbandingan Algoritma Knuth-Morris-Pratt dan Algoritma Boyer-Moore
matriks n x n •Ukuran panjang bidang papan permainan dinamis •Pengujian menggunakan beberapa pola kata dari beberapa panjang kalimat yaitu 3-10 karakter dan menggunakan 8 sampel dengan posisi random •Pengujian kata-kata diambil dari nama-nama hewan dalam Bahasa Indonesia.
ketemu ubah cara baca 2. Kanan ke kiri, jika tidak ketemu ubah cara baca 3. Atas ke bawah, jika tidak ketemu ubah cara baca 4. Bawah ke atas, jika tidak ketemu ubah cara baca 5. Secara diagonal dari kiri atas ke kanan bawah, jika tidak ketemu ubah cara baca 6. Secara diagonal dari kanan bawah ke kiri atas, jika tidak ketemu ubah cara baca 7. Secara diagonal dari kanan atas ke kiri bawah, jika tidak ketemu ubah cara baca 8. Secara diagonal dari kiri bawah ke kanan atas, , jika tidak ketemu ubah cara baca
L A M I N G O 0 0 0 0 0 0 0 0 Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O 1) 2) Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O F L A M I N G O 0 0 0 0 0 0 0 0 F L A M I N G O 0 0 0 0 0 0 0 0 Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O 3) Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter
Tidak terjadi ketidakcocokan, maka pattern digeser sejumlah 1 karakter Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O F L A M I N G O 0 0 0 0 0 0 0 0 F L A M I N G O 0 0 0 0 0 0 0 0 Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O 5) Tahap pencarian dengan algoritma Knuth-Morris-Pratt selesai setelah melakukan sebanyak 4 iterasi
Index = Panjang (pattern)-2 F L A M I N G O Pindah = 1 Bandingkan “G” dengan “Null Hasil BmBc(sebelum) BmBc(sesudah) Karakter Null Karakter G Nilai OH Null Nilai OH 1 1) Tabel comparator BmBc Mulai : Index = Panjang (pattern)-3 F L A M I N G O Pindah = 2 Bandingkan “N” dengan “G" Hasil BmBc(sebelum) BmBc(sesudah) Karakter G Karakter N G Nilai OH 1 Nilai OH 2 1 2) Tabel comparator BmBc
Index = Panjang (pattern)-4 F L A M I N G O Pindah = 3 Bandingkan “I” dengan “G “,”N” Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N Karakter I N G Nilai OH 1 2 Nilai OH 3 2 1 3) Tabel comparator BmBc Mulai : Index = Panjang (pattern)-5 F L A M I N G O Pindah = 4 Bandingkan “M” dengan “G“,”N”,” I” Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I Karakter M I N G Nilai OH 1 2 3 Nilai OH 4 3 2 1 4) Tabel comparator BmBc
Index = Panjang (pattern)-6 F L A M I N G O Pindah = 5 5) Tabel comparator BmBc Mulai : Index = Panjang (pattern)-7 F L A M I N G O Pindah = 6 6) Tabel comparator BmBc Bandingkan “A” dengan “G“,”N”,” I”,”M” Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I M Karakter A M I N G Nilai OH 1 2 3 4 Nilai OH 5 4 3 2 1 Bandingkan “L” dengan “G“,” N”,”I”,”M”,”A” Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I M A Karakter L A M I N G Nilai OH 1 2 3 4 5 Nilai OH 6 5 4 3 2 1
Index = Panjang (pattern)-1 F L A M I N G O Pindah = 7 7) Tabel comparator BmBc Mulai : Index = Panjang (pattern)-1 F L A M I N G O Pindah = 8 8) Tabel comparator BmBc Bandingkan “O” dengan “G“,” N”,”I”,”M”,”A”,”L”,”F” Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I M A L F Karakter F L A M I N G 0 Nilai OH 1 2 3 4 5 6 7 Nilai OH 7 6 5 4 3 2 1 0 Bandingkan “F” dengan “G“,”N”,” I”,”M”,”A”,”L” Hasil BmBc(sebelum) BmBc(sesudah) Karakter G N I M A L Karakter F L A M I N G Nilai OH 1 2 3 4 5 6 Nilai OH 7 6 5 4 3 2 1
1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 1 Suffix Index 7 Move Prefix O Suffix NULL Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? 1) 2) Suffix Index 6 Move Prefix G Suffix O Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 1
1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 1 Suffix Index 5 Move Prefix N Suffix GO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? 3) 4) Suffix Index 4 Move Prefix I Suffix NGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 1
1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 1 Suffix Index 3 Move Prefix M Suffix INGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? 5) 6) Suffix Index 2 Move Prefix A Suffix MINGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 8 1
1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 8 8 1 Suffix Index 1 Move Prefix L Suffix AMINGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? 7) 8) Suffix Index 0 Move Prefix F Suffix LAMINGO Suffix comparator FLAMING 1 FLAMIN 2 FLAMI 3 FLAM 4 FLA 5 FL 6 F 7 NULL 8 MH value ? Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai MH 8 8 8 8 8 8 8 1
= BmBc[M] -7 + 7 atau Max (1 = 4 - 7 + 7 ) = 4 2) BmBc & BmGs Index 0 1 2 3 4 5 6 7 Karakter F L A M I N G O Nilai OH 7 6 5 4 3 2 1 0 Nilai MH 8 8 8 8 8 8 8 1 Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O Teks : Y H X B F L A M I N G O H Z V Pattern : F L A M I N G O Tahap pencarian dengan algoritma Boyer-Moore diatas pencarian selesai setelah melakukan sebanyak 1 iterasi.
30x30,40x40 dan 50x50 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 4 kali sesuai dengan bidang papan dengan kondisi pola kata random
papan 20x20 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
papan 30x30 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
papan 40x40 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
papan 50x50 Jumlah kata terdapat 8 kata dengan panjang 3-10 karakter dengan posisi random Pengujian akan dilakukan 8 kali sesuai dengan banyak kata dengan kondisi posisi pola terpenuhi semua.
Pencarian pada posisi diagonal dapat menambah waktu pencarian pada kedua algoritma Knuth-Morris-Pratt dan algoritma Boyer-Moore Parameter seperti panjang papan, posisi pola dan panjang kata dapat mempengaruhi efisiensi algoritma pencarian string pada algoritma Knuth-Morris-Pratt