Algoritma pencarian adalah suatu metode yang digunakan untuk menyelesaikan masalah pencarian khususnya pada implementasi di bidang teknologi informasi. Salah satu algoritma yang dikenal cukup efisien dalam melakukan pencarian adalah algoritma Knuth-Morris-Pratt. Algoritma ini bekerja dengan mencari perulangan pola pada sebuah sususan array yang dicari yang selanjutnya digunakan sebagai acuan untuk melakukan pencarian lebih singkat. Pada jurnal yang berjudul “Aplikasi Algoritma Pencarian String Knuth-Morris-Pratt dalam Permainan Word Search”, telah dibuktikan bahwa algoritma pencarian Knuth-Morris-Pratt ini dapat diimplementasikan pada sebuah permainan puzzle. Namun, hasil performansi dan hasil implementasinya tidak terdokumentasi dan tidak pula diperbandingkan dengan metode pencarian lain, sehingga dari penelitian itu belum dapat disimpulkan apakah algoritma KMP ini secara relatif lebih baik dibandingkan dengan suatu algoritma pencarian lain untuk implementasinya dalam suatu permainan puzzle.Dari permasalahan yang telah disebutkan, maka algoritma KMP ini akan dibandingkan performansinya dengan metode pencarian Brute Force dengan mengimplementasikan kedua algoritma tersebut ke dalam sebuah permainan teka-teki warna. Parameter hasil pencarian yang akan diukur adalah banyaknya memori yang digunakan, banyaknya perulangan yang dilakukan dan batas maksimal masing-masing algoritma melakukan perulangan dengan menggunakan standar big-O.Dari hasil penelitian menunjukkan bahwa algoritma pencarian Knuth-Morris-Pratt relatif lebih cepat karena melakukan perulangan lebih sedikit dan lebih terskala dalam hal kompleksitas waktu yang artinya maksimal perulangan relatif lebih kecil dibandingkan dengan algoritma pencarian Brute Force. Namun algoritma Knuth-Morris-Pratt membutuhkan space memori lebih besar dibandingkan dengan algoritma Brute Force karena algoritma KMP menyimpan tambahan informasi berupa overlap, yaitu informasi tentang pola-pola yang berulang.

The search algorithm is a method used to solve the search problem, especially in the implementation of information technology field. One of the algorithms that is known to be quite efficient in performing search is Knuth-Morris-Pratt algorithm.The algorithm works by finding a loop pattern in the arrangement of the searched array for later used as a reference for a shorter search. In a journal entitled "Knuth-Morris-Pratt String Search Algorithm Application in the Word Search game", has been proven that the Knuth-Morris-Pratt search algorithm can be implemented in a puzzle game. However, the results of the performance and results of their implementation are not documented nor compared with other search methods, so that the research cannot be concluded whether this KMP algorithm is relatively better than other search algorithms for an implementation in a puzzle game.From the problem that has been mentioned, this KMP performance will be compared with that of the Brute Force search method by implementing both algorithms in a color puzzle game. Search result parameters that will be measured are how much memory is used, the number of iterations performed and the maximum loop limit of each algorithm using the big-O standard. Research result shows that the Knuth-Morris-Pratt search algorithm searches relatively faster for less loops are performed and more scalable in terms of time complexity, which means the maximum iteration time is relatively small compared to the Brute Force search algorithm. However, the Knuth-Morris-Pratt algorithm require more memory space than the Brute Force algorithm because KMP algorithm stores additional information such as overlap, ie information about the repetitive patterns.

https://elib.unikom.ac.id/gdl.php?mod=browse&op=read&id=jbptunikompp-gdl-falihmulya-35238