## PENERAPAN ALGORITMA PENCARIAN KNUTH-MORRIS-PRATT (KMP) DALAM SISTEM INFORMASI PERPUSTAKAAN SMK TI PRATAMA
Nursobah 1) dan Pajar Pahrudin 2)
1 Teknik Informatika,STMIK Widya Cipta Dharma
2 Sistem Informasi, STMIK Widya Cipta Dharma
1,2 M.Yamin No 25, Samarinda E-mail : nursobah2011@gmail.com 1) , pajar@wicida.ac.id 2)

## ABSTRAK
Perpustakaan  SMK  TI  Pratama  merupakan  sumber  pengetahuan  siswa  yang  dapat  meningkatkan  kualitas  pengetahuan siswa.  Sebagian  besar  perpustakaan  sekolah  swasta  di  samarinda  masih  menggunakan  sistem  pencarian  manual  untuk mencari  katalog  perpustakaan.  Sistem  yang  belum  terkomputerisasi  tersebut  menyebabkan  kegiatan  operasional perpustakaan  berjalan  lambat  dan  tidak  efektif  terutama  pada  penelusuran  katalog  perpustakaan.  Maka  dari  itu  untuk mengatasi  masalah  penelusuran  katalog  dibuat  sistem  penelusuran  katalog  perpustakaan  sekolah  dengan mengimplementasikan  algoritma Knuth-Morris-Pratt (KMP).  Algoritma Knuth-  Morris-Pratt merupakan  algoritma pencarian string dengan melakukan perbandingan karakter mulai dari karakter paling kanan dari string yang dicari. Sistem penelusuran  katalog  perpustakaan  sekolah  dengan  mengimplementasikan  algoritma Knuth-Morris-Pratt dapat mempermudah pengunjung perpustakaan sekolah untuk mengetahui jumlah dan keberadaan buku yang akan dipinjam dan mempermudah pustakawan untuk mengelola buku perpustakaan
Kata Kunci: Knuth Morris Pratt, Pencariam, Katalog Perpustakaan, SMK TI Pratama,
1. PENDAHULUAN
Fungsi dan wujud dari perpustakaan terus berkembang  seiring  dengan  perkembangan  peradaban manusia  dari  mulai  zaman  batu,  ketika  manusia menyimpan  sumber  pengetahuan  pada  lempengan  batu sampai  kini  berada  pada  awal  millenium  ketiga  yang mana sumber pengetahuan sudah banyak yang disimpan dalam  bentuk  digital  yaitu  format  dari  sumber pengetahuan  yang  dapat  dimengerti  oleh  komputer, apalagi  dengan  adanya  internet  perpustakaan  menjadi lebih  fungsional.  Peranan  perpustakaan  harus  mampu menunjukkan  identitasnya  sebagai  penyedia  informasi yang  representative  dalam  arti  yang  seluas-luasnya (Putera dan Ibrahim, 2018).
Artinya  kehidupan  dan  keberadaan  perpustakaan dapat  menjadi  rantai  sejarah  bagi  masa  lalu,  akar  bagi hidup  dimasa  sekarang  ini  dan  pembimbing  untuk melangkah kemasa depan. Adapun tujuan diselenggarakannya perpustakaan adalah untuk mendukung,  memperlancar  serta  mempertinggi  kualitas pelaksanaan program  kegiatan perguruan tinggi melalui pelayanan  informasi  yang  meliputi  lima  aspek  yaitu pengumpulan informasi, pelestarian informasi, pengolahan  informasi,  pemanfaatan  informasi  dan penyebarluasan    informasi  sebagian  besar  perpustakaan sekolah  swasta  masih  menggunakan  sistem  pencarian manual  untuk  mencari  buku  bukunya,    hal  ini  juga terjadi  di  SMK  TI  Pratama.  Sistem  yang  belum terkomputerisasi tersebut menyebabkan kegiatan operasional  perpustakaan  berjalan  lambat  dan  tidak efektif  terutama  peneluran  koleksi  perpustakaan  yang
masih harus dilakukan secara manual,  pengunjung harus bertanya  dulu  kepada  admin,  apakah  buku  yang  dicari tersedia (Pratiwi et al,2018).
Sehingga  diperlukan  suatu  sistem  informasi  yang dapat  memecahkan  permasalahan  tersebut  sehingga dapat  mempermudah  pengunjung  perpustakan.  Sistem penelusuran katalog perpustakaan sekolah yang akan di bangun  memerlukan  algoritma  pencarian string yang cepat dan efektif. Implementasi algoritma Knuth-Morris- Pratt (KMP)  ke  dalam  sistem  penulusuran  katalog perpustakaan  sekolah  dapat  membuat  penelusuran katalog  lebih  cepat  dan  akurat  sehingga  pelayanan perpustakaan  dapat  berjalan  lancar.  Kelebihan  dari algoritma Knuth-  Morris-Pratt selain  cepat  juga  sangat baik  digunakan  pada  file  berukuran  besar  karena pencarian  kecocokan  tidak  perlu  kembali  ke  belakang pada input teks (Sunarto,2018).

## 2. RUANG LINGKUP
Dalam penelitian ini permasalahan mencakup:
1. Bagaimana  membangun  sebuah  sistem  informasi perpustakaan  yang  memiliki  katalog  pencarian dengan cepat
2. Bagaimana  mengimplementasikan  algoritma  KMP dalam sistem  untuk mengetahui ketersediaan koleksi buku yang akan dipinjam
3. BAHAN DAN METODE
Penelitian tentang Algoritma pencarian telah banyak dilakukan antara lain :
1. Penerapan algoritma KMP pada posting twitter TMC polda  metro  jaya  untuk  melaporkan  kondisi lalulintas dan rute jalan kota Jakarta, pada penelitian ini,  algoritma Knuth-Morris-Pratt dilakukan  untuk pencarian  nama  jalan  atau  lokasi  beserta  kondisi lalulintasnya, kemudian dilakukan visualisasi menggunakan Google  Map ,  sehingga  ketika  user memilih  lokasi  tujuan  perjalanan  dari  suatu  tempat ke  tempat  lainnya  di  kota  Jakarta  maka  akan ditampilkan rute jalan beserta kondisi lalulintasnya(Setiawan,2015).
2. Perbandingan  algoritma Knuth-Morris-Pratt dan Turbo  Boyer-Moore  dalam  Query  MySQL,  pada penelitian  ini  membahas  perbandingan  kecepatan penelusuran  basis  data  berdasarkan  query  SQL. Dalam  basis  data  dibutuhkan  kecepatan  yang  tinggi agar  proses  yang  menggunakan  informasi  tersebut dapat berjalan efektif (Siahaan,2010)
Sedangkan  pada  penelitian  ini.  algoritma  yang diterapkan  adalah  KMP  diterapkan  untuk  penelusuran katalog perpustakaan sekolah, dalam membuat penelusuran  katalog  memerlukan  algoritma  pencarian string  yang  cepat,  efektif  dan  lebih  akurat  sehingga pelayanan perpustakaan dapat berjalan dengan lancar.

## 3.1 Knuth-Morris-Pratt
Algoritma Knuth-Morris-Pratt adalah  salah  satu algoritma  pencarian  string,  dikembangkan  secara terpisah  oleh  Donald  E.  Knuth  pada  tahun  1967  dan James H. Morris bersama Vaughan R. Pratt pada tahun 1966,  namun  keduanya  mempublikasikannya  secara bersamaan  pada  tahun  1977  (Manikandan  dan Ramyachitra,2018).
Jika  kita  melihat  algoritma  KMP  lebih  mendalam, kita  mengetahui  bahwa  dengan  mengingat  beberapa perbandingan  yang  dilakukan  sebelumnya  kita  dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan  menghemat  perbandingan,  yang  selanjutnya  akan meningkatkan kecepatan pencarian.
Perhitungan  penggeseran  pada  algoritma  ini  adalah sebagai  berikut,  bila  terjadi  ketidakcocokkan  pada  saat pattern sejajar dengan teks[i..i+n-1] , dapat menganggap ketidakcocokan  pertama  terjadi  di  antara teks[i+j] dan pattern[j] , dengan 0<j<n . Berarti, teks[i..i+j- 1]=pattern[0..j-1] dan a=teks[i+j] tidak  sama  dengan b=pattern[j]. Ketika  kita  menggeser,  sangat  beralasan bila ada sebuah awalan v dari pattern akan sama dengan sebagian  akhiran u dari  sebagian  teks.  Sehingga  kita bisa  menggeser  pattern  agar  awalan v tersebut  sejajar dengan akhiran dari u.
Dengan  kata  lain,  pencocokkan  string akan  berjalan secara  efisien  bila  kita  mempunyai  tabel  yang menentukan berapa panjang kita seharusnya  menggeser seandainya terdeteksi ketidakcocokkan di karakter ke- j dari  pattern.  Tabel  itu  harus  memuat next[j] yang merupakan  posisi  karakter pattern[j] setelah  digeser, sehingga  kita  bisa  menggeser  pattern  sebesar j-next[j] relatif  terhadap  teks.  (Sunarto,2018;Jimale  et  al,2018).
Secara  sistematis,  langkah-langkah  yang  dilakukan algoritma  Knuth-Morris-Pratt  pada  saat  mencocokkan string:
1. Algoritma  Knuth-Morris-Pratt  mulai  mencocokkan pattern pada awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang  bersesuaian,  sampai  salah  satu  kondisi  berikut dipenuhi:
1) Karakter dipattern dan di teks yang dibandingkan tidak cocok (mismatch).
2) Semua  karakter  di  pattern  cocok.  Kemudian algoritma  akan  memberitahukan  penemuan  di posisi ini.
3. Algoritma kemudian menggeser pattern berdasarkan tabel next, lalu mengulangi langkah 2 sampai pattern berada di ujung teks.

## 3.2 Metode Air Terjun
Model  air  terjun  ( waterfall )  adalah  model  satu  arah yang  dimulai  dari  tahap  persiapan  sampai  perawatan, dan  model  inilah  yang  dipakai  oleh  penulis  dalam menganalisa sistem yang akan dikerjakan
1. Analisis data sistem ini bertujuan untuk memberikan gambaran tentang sistem yang diusulkan, menganalisa teknologi yang dibutuhkan
2. Desain  sistem  ini  bertujuan  untuk  memberikan gambaran  umum  tentang  sistem  yang  diusulkan. Desain  yang  digunakan  adalah Diagram  Alir (Flowchart )
3. Coding & Testing yaitu dalam hal ini difokuskan pada pembuatan program dan penggunaannya. Pada tahap ini bertujuan untuk meletakkan algoritma KMP yang di buat agar siap untuk dioperasikan atau dijalankan.
4. Penerapan  /  pengujian  program , Metode  pengujian ini  menggunakan  metode  pengujian white-  box . Pengujian  ini  digunakan  untuk  untuk  memastikan bahwa  semua  statemen  pada  program  telah dieksekusi  paling  tidak  satu  kali  selama  pengujian dan bahwa semua kondisi logis telah diuji
5. Pemeliharaan Perangkat lunak yang sudah disampaikan kepada pelanggan pasti akan mengalami  perubahan.  Perubahan  tersebut  bisa karena mengalami kesalahan karena perangkat lunak harus  menyesuaikan  dengan  lingkungan  (periperal atau  sistem  operasi  baru)  baru,  atau  karena pelanggan membutuhkan perkembangan fungsional.
Setiap  tahapan  dilakukan  secara  berurutan  mulai  dari langkah  pertama  sampai  langkah  terakhir,  setiap langkah  yang  telah  selesai  dikerjakan  harus  dilakukan pengkajian ulang, tertera dalam gambar 1 berikut :
Gambar 1. Gambaran Sistem

## 4. PEMBAHASAN
Berikut disajikan hasil analisis dan implementasi dari penerapan algoritma pada sistem yang dibangun

## 4.1 Analisa  Implementasi  algoritma  Knuth  Morris Pratt dalam sistem pencarian buku
Secara  sistematis,  langkah-langkah  yang  dilakukan algoritma  Knuth  Morris  Pratt  pada  saat  mencocokkan string yaitu (Ramadhani, 2017):
1. Masukkan  Query  kata  yang  akan  dicari.  Dengan permisalan    P    =    Pattern    atau    pola  susunan  kata yang  dijadikan  sebagai  contoh  atau  pola  teks  yang akan dicari T = Teks atau judul dokumen.
2. Algoritma  Knuth  Morris  Pratt  mulai  mencocokkan pattern  atau  pola  susunan  kata  yang  dijadikan sebagai contoh pada awal teks.
3. Dari kiri ke  kanan, algoritma  ini akan  mencocokkan karakter  per  karakter  patternatau  pola  susunan  kata yang  dijadikan  sebagai  contoh  dengan  karakter  di teks  yang  bersesuaian,  sampai  salah  satu  kondisi berikutdipenuhi yaitu :
1) Karakter  di  patternatau  pola  susunan  kata  yang dijadikan  sebagai  contoh  dan  di  teks  yang dibandingkan tidak cocok (mismatch).
2) Semua  karakter di patternatau pola susunan  kata yang  dijadikan  sebagai  contoh  cocok.  Kemudian algoritma  akan  memberitahukan  penemuan  di posisi ini.
4. Algoritma  kemudian  menggeser  patternatau  pola susunan  kata  yang  dijadikan  sebagai  contoh berdasarkan tabel next, lalu mengulangi langkah no. 2  sampai  patternatau  pola  susunan  kata  yang dijadikan sebagai contoh berada di ujung teks.
Perhitungan manual pada algoritma Knuth- Morris-Pratt digunakan  untuk  membuat  gambaran  kasar  dari  cara kerja algoritma tersebut. Data pada perhitungan  manual ini diambil dari salah  satu  data  nyata  yang  ada  pada database terlihat pada tabel 1 sampai 7.
String : risalah Pattern : salah
Tabel 1. Pattern tidak cocok dengan string String R i s a l a h Pattern S a l a h
LangkahI  :Pattern  tidak  cocok  dengan  string.  Maka pattern akan bergeser satu posisi ke kanan.
Tabel 2. Pattern tidak cocok dengan string kembali String R i s a l a h Pattern S A l a h
LangkahII:  Pattern  tidak  cocok  dengan  string.  Maka pattern akan bergeser satu posisi ke kanan.
Tabel 3. Pencocokan pattern dengan string kembali String R i S a l a h Pattern S a l a h
LangkahIII:  Pattern  cocok  dengan  string.  Karena  ada keocokan,  maka  algoritma  Knuth  Morris  Pratt  akan menyimpan  informasi  ini,  dan  pattern  tidak  akan melakukan  pergeseran  dan  melanjutkan  pencocokan pattern dengan string.

## Tabel 4. Pattern cocok dengan string
LangkahIV  :  Pattern  cocok  dengan  string.  Karena  ada keocokan,  maka  algoritma  Knuth  Morris  Pratt  akan menyimpan  informasi  ini,  dan  pattern  tidak  akan melakukan  pergeseran  dan  melanjutkan  pencocokan pattern dengan string.
Tabel 5. Pattern cocok dengan string kembali String
R
i s a l a h Pattern S a l
a h
LangkahV  :  Pattern  cocok  dengan  string.  Karena  ada keocokan,  maka  algoritma  Knuth  Morris  Pratt  akan menyimpan  informasi  ini,  dan  pattern  tidak  akan melakukan  pergeseran  dan  melanjutkan  pencocokan pattern dengan string.
Tabel 6. Pattern cocok dengan string indeks ke-6
String R
i s a l a h Pattern S a l a h
LangkahVI  :  Pattern  cocok  dengan  string.  Karena  ada keocokan,  maka  algoritma  Knuth  Morris  Pratt  akan menyimpan  informasi  ini,  dan  pattern  tidak  akan melakukan  pergeseran  dan  melanjutkan  pencocokan pattern dengan string.
String R i s a l a h Pattern S a l a h
Tabel 7. Pattern cocok dengan string indeks ke-7 String R i s a l a h Pattern S a l a h
LangkahVII  :  Pattern  cocok  dengan  string.  Karena  ada keocokan,  maka  algoritma  Knuth  Morris  Pratt  akan menyimpan  informasi  ini,  dan  pattern  tidak  akan melakukan  pergeseran  dan  melanjutkan  pencocokan pattern  dengan  string.  Namun  karena  jumlah  pattern hanya  6  huruf,  maka  pencarian  akan  dihentikan  dan diperoleh  hasil  bahwa  pattern  P  terdapat  kecocokan dengan string S sebesar 100 persen.

## 4.2 Tampilan Antarmuka Pencarian Dalam Sistem
Berikut  ini  merupakan  tampilan  dari form pencarian buku,  pada form  user menginputkan  buku  akan menampilkan  data  alternatif  dari database yang  sudah diinputkan.

## Gambar 2. Tampilan Antarmuka

## 5. KESIMPULAN
Kesimpulan  yang  diperoleh  dari  penelitian  adalah dengan mengimplementasikan Algoritma Knuth- Morris- Pratt dapat  membantu  meringankan  kerja  petugas  atau admin  dalam  memberi  laporan  jumlah  buku  yang tersedia  diperpustakaan,  dan  juga  dalam  melayani pengunjung  yang  ingin  mengetahui  koleksi  buku diperpustakaan SMK TI Pratama.

## 6. SARAN
Untuk  perkembangan  dapat  menambahkan  aplikasi simpan  pinjam  buku  dan  pengembalian  buku.  Dan Algoritma Knuth  Morris  Pratt dapat  digantikan  dengan algoritma  pencarian  string  yang  lain  seperti  algoritma Boyer Moore.

## 7. DAFTAR PUSTAKA
Jimale, A. O., Zainon, W. M. N. W., & Abdullahi, L. F. 2018.  Spell  Checker  for  Somali  Language  Using Knuth-Morris-Pratt String Matching Algorithm. In
International  Conference  of  Reliable  Information and  Communication  Technology  (pp.  249-256). Springer, Cham
Manikandan,  P.,  &  Ramyachitra,  D.  2018.  PATSIM:
Prediction  and  analysis  of  protein  sequences using    hybrid    Knuth-Morris    Pratt    (KMP)    and Boyer-Moore     (BM)     algorithm.  Gene,  657, 50- 59.
Pratiwi,  D.,  Hartini,  S.,  &  Marlina,  S.  2018.  Rancang Bangun  Sistem  Informasi  Perpustakaan  Pada Sekolah SMK Yadika 13 Tambun  Utara Berbasis WEB. Paradigma-Jurnal Komputer dan Informatika, 20(1), 53-58.
Putera,  A.  R.,  &  Ibrahim,  M.  2018.  Rancang  Bangun Sistem  Informasi  Peminjaman  dan  Pengembalian Buku  Perpustakaan  SMP  Negeri  1  Madiun. Doubleclick: Journal of Computer and Information Technology, 1(2), 57-61.
Ramadhani,  d.  2017.  Perancangan  aplikasi  pencarian buku  pada  perpustakaan  islamic  international school  darul  ilmi  murni  dengan  algoritma  knuth morris  pratt. Pelita  informatika:  informasi  dan informatika , 16 (1).
Setiawan, Rudi. 2015. Penerapan Algoritma KMP Pada Posting  Twitter  TMC  Polda  Metro  Jaya  Untuk Melaporkan  Kondisi  Lalulintas  Dan  Rute  Jalan Kota Jakarta. Jurnal Informatika Vol 9. Jakarta.Hal 10-16 http://journal.uad.ac.id
Siahaan,  Margaretha.  2010.  Perbandingan  Algoritma Knuth-Morris-Pratt  fan  Turbo  Boyer-  Moore Dalam  Query  MySQL.  Makalah  IF3051  Strategi Algoritma. Bandung. Hal 1-5
http://informatika.stei.itb.ac.id
Sunarto,  Y.  K.  2018.  Studi  Perbandingan  Algoritma Naive  Method,  Knuth-Morris-Pratt  dan  Boyer- Moore-Hoorspool  pada  Multi  Record  Database (Doctoral  dissertation,  Program  Studi  Teknik Informatika FTI-UKSW).

## UCAPAN TERIMA KASIH
Dengan segala kerendahan hati, penulis ingin mengucapkan terima kasih kepada
Allah SWT atas rahmat dan karunia-Nya
Direktorat Riset dan Pengabdian Masyarakat, Direktorat Jenderal Penguatan Riset dan Pengembangan Kementerian Riset, Teknologi, dan Pendidikan Tinggi sesuai dengan Kontrak Penelitian Tahun Anggaran 2019
Dan kepada teman-teman yang telah banyak membantu dan memberikan motivasinya