Analisis Perbandingan Algoritma Knuth-Morris-Pratt Dengan Algoritma Boyer-Moore Pada Permainan Word Search Puzzle

Permainan word search puzzle adalah permainan berbasis puzzle yang mencari kata-kata yang disusun dalam bentuk array dua dimensi atau yang lebih dikenal dengan matriks. Kata-kata tersebut dapat disusun secara horizontal, vertikal maupun diagonal dan dapat ditulis pada posisi terbalik. Penyelesaian dari permainan word search puzzle ini adalah menemukan semua kata yang tersembunyi di papan permainan yang berbentuk matriks. Permasalahan yang dihadapi adalah bagaimana sistem dapat menemukan semua kata yang tersembunyi di dalam puzzle yang telah tersusun secara random baik secara horizontal, vertikal, maupun diagonal atau sebaliknya. Hasil dari penelitian ini bahwa algoritma Boyer-Moore lebih efisien pada pencarian dengan arah kiri ke kanan, kanan ke kiri , atas ke bawah dan bawah ke atas atau vertikal dan horizontal. Hal ini dikarenakan teks yang diekstrak untuk pencocokan pola dengan arah pencarian vertikal dan horizontal jumlahnya sama panjang, sedangkan algoritma Knuth-Morris-Pratt lebih efisien pada tahap pencarian diagonal dengan arah dari diagonal kiri atas ke kanan bawah, diagonal kanan bawah ke kiri atas, diagonal kanan atas ke kiri bawah dan diagonal kiri bawah ke kanan atas. Hal ini dikarenakan teks yang diekstrak untuk pencocokan pola dengan arah diagonal jumlahnya tidak sama panjang.

Word search puzzle games is a game puzzle-based which searching for the words listed in a form of two dimension array or more known as matrix. The words can be compiled horizontally, vertically, or even diagonally also can be written upside down. The completion of the game word search puzzle is finding all the words hidden on the game board in the shape of a matrix. The problem is how the system find all the hiding words in the puzzle which has random compiled whether it is horizontally, vertically, diagonally or otherwise. The result from this research that Boyer-Moore algorithm is more efficient on the search with the direction left to right, right to left, top to bottom and bottom to top or vertical and horizontal. It was because the text extracted for matching pattern to the vertical and horizontal direction search has the same length, where as Knuth-Morris-Pratt algorithm is more efficent in the diagonal search which is diagonally upper left to the lower right, diagonally lower right to the upper left, diagonally upper right to the lower left, and diagonally lower left to the upper right. It was because the text extracted for matching pattern diagonal direction search has not the same length.