IMPLEMENTASI ALGORITMA KNUTH MORRIS PRATT DAN MAXIMAL SHIFT PADA STRING MATCHING

Aplikasi Lowkey match dapat membantu masyarakat untuk mempermudah pencarian kata pada dokumen yang memiliki jumlah karakter kata yang banyak. Maka, dari itu dibutuhkan algoritma String Matching untuk memudahkan pencarian kata pada aplikasi tersebut, terdapat beberapa algoritma String Matching yaitu; Knuth Morris Pratt dan Maximal Shift. Dalam proses pencarian kata algoritma Knuth Morris Pratt dan Maximal Shift memiliki cara kerja yang berbeda. Maximal Shift adalah algoritma yang mencari pola dalam teks dengan cara pola dicari dari karakter yang memiliki nilai minShift yang terbesar hingga minShift yang terkecil dan perbandingan pola yang dilakukan dari kanan ke kiri. Sedangkan, Knuth Morris Pratt adalah algoritma yang akan mencocokkan pattern atau susunan kata yang akan dicari dari kiri ke kanan pada awal teks dan kemudian menggeser susunan kata sampai susunan kata tersebut berada di ujung teks. Aplikasi Lowkey match ini akan menampilkan pencarian kata serta perbandingan running time kedua algoritma. Dari hasil pencarian kata terdapat nilai rata-rata running time pada algoritma Knuth Morris Pratt yaitu 6.625 ms dan Maximal Shift yaitu 10.875 ms. Dari nilai rata-rata tersebut dapat disimpulkan bahwa algoritma Knuth Morris Pratt lebih cepat dalam melakukan pencarian kata.