Knuth Morris Pratt String Matching Algorithm in Searching for Zakat Information and Social Activities

Fendi Riawan, Taqwa Hariguna

Abstract


Algorithms are one of the components that need to be considered in the development of information systems. Determination of the algorithm is adjusted to the purpose of the system to be built. One algorithm that can be used is string matching. The string matching algorithm will play a role in searching for a string consisting of several characters (usually called a pattern). The method used in this research is string matching knuth morris pratt (KMP) which is used to search zakat information and social activities in the search engine system. KMP is a string matching algorithm with good performance. The results showed the performance of string matching using the KMP algorithm with 5 trials of input pattern on zakat information with execution times of 0.03 ms, 0.03 ms, 0.02 ms, 0.02 ms and 0.03 ms. And 5 times the input pattern experiment on social activities with execution time of 0.02 ms, 0.02 ms, 0.03 ms, 0.03 ms and 0.02 ms. Thus the average execution time of the KMP algorithm in string matching is 0.026 ms and 0.024 ms.


Article Metrics

Abstract: 85 Viewers PDF: 59 Viewers

Keywords


String Matching Algorithm; Knuth Morris Pratt; Pattern; Search Engine

Full Text:

PDF


References


A. R. Hakim, K. Nasution, O. K. Sulaiman, and M. Z. Siambaton, “Perancangan Aplikasi Skripsi Online Menggunakan Algoritma String Matching Knuth Morris-Pratt Pada Fakultas Teknik Universitas Islam Sumatera Utara,” J. Ilmu Komput. dan Inform., vol. 03, no. 2598–6341, pp. 98–107, 2019.

M. Syarif, “Implementasi Algoritma String Matching Dalam Pencarian Surah Dan Ayat Dalam Al-Quran Berbasis Web,” Indones. J. Netw. Secur., vol. 6, no. 2, pp. 70–76, 2017.

A. B. Vavrenyuk, V. V Makarov, and V. A. Shurygin, “The substring search algorithm in the biotechnological processes simulation,” Int. J. Pure Appl. Math., vol. 118, no. 5, pp. 701–709, 2018.

T. H. Sa’diah, “Implementasi Algoritma Knuth-Morris-Pratt Pada Fungsi Pencarian Judul Tugas Akhir Repository,” J. Komputasi, vol. 14, no. 1, pp. 115–125, 2017.

M. R. Hossen, M. S. Azam, and H. K. Rana, “Performance Evaluation of Various DNA Pattern Matching Algorithms Using Different Genome Datasets,” Accel. world’s Res., vol. 3, no. 1, 2018, doi: 10.5281/zenodo.2580651.

R. Y. Tsarev, A. S. Chernigovskiy, E. A. Tsareva, V. V. Brezitskaya, A. Y. Nikiforov, and N. A. Smirnov, “Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms,” IOP Conf. Ser. Mater. Sci. Eng., vol. 122, no. 1, 2016, doi: 10.1088/1757-899X/122/1/012034.

Nuraini and B. Firmansyah, “IMPLEMENTASI ALGORITMA KNUTH MORRIS PRATH UNTUK KAMUS TERJEMAHAN DIGITAL ACEH – BAHASA INDONESIA BERBASIS WEB,” J. Nas. Inform., vol. 1, no. 1, pp. 66–75, 2020.

M. M. Y. Daeli and R. K. Hondro, “Perancangan Aplikasi Pencarian Kata dengan Kombinasi Algoritma Knuth Morris Pratt dan Algoritma Boyer Moore,” Maj. Ilm. INTI, vol. XII, no. 2, pp. 271–275, 2017, [Online]. Available: https://ejurnal.stmik-budidarma.ac.id/index.php/inti/article/view/380/362.

A. F. Qur’ani, “Penerapan Algoritma String Matching Knuth-Morris- Pratt Untuk Mencari Modifikasi Pada Kode,” Makal. IF2211 Strateg. Algoritm. Inst. Teknol. Bandung, 2021.

W. Astuti, “Analisis String Matching Pada Judul Skripsi Dengan Algoritma Knuth-Morris Pratt (Kmp),” Ilk. J. Ilm., vol. 9, no. 2, pp. 167–172, 2017, doi: 10.33096/ilkom.v9i2.136.167-172.

C. B. G. Maldonado, M. S. Penas, and M. V. L. Lopez, “Negative Selection and Knuth Morris Pratt Algorithm for Anomaly Detection,” IEEE Lat. Am. Trans., vol. 14, no. 3, pp. 1473–1479, 2016, doi: 10.1109/TLA.2016.7459637.

K.-J. Lin, Y.-H. Huang, and C.-Y. Lin, “Efficient Parallel Knuth-Morris-Pratt Algorithm for Multi-GPUs with CUDA BT - Advances in Intelligent Systems and Applications - Volume 2,” in IOP Conference Series: Earth and Environmental Science, 2013, pp. 543–552.

R. Rahim, I. Zulkarnain, and H. Jaya, “A review: Search visualization with Knuth Morris Pratt algorithm,” IOP Conf. Ser. Mater. Sci. Eng., vol. 237, no. 1, pp. 1–6, 2017, doi: 10.1088/1757-899X/237/1/012026.

R. Y. Tsarev, A. S. Chernigovskiy, E. A. Tsareva, V. V. Brezitskaya, A. Y. Nikiforov, and N. A. Smirnov, “Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms,” IOP Conf. Ser. Mater. Sci. Eng., vol. 122, no. 1, 2016, doi: 10.1088/1757-899X/122/1/012034.

S. Aygün, E. O. Güneş, and L. Kouhalvandi, “Python based parallel application of Knuth-Morris-Pratt algorithm,” in 2016 IEEE 4th Workshop on Advances in Information, Electronic and Electrical Engineering (AIEEE), 2016, pp. 1–5, doi: 10.1109/AIEEE.2016.7821801.

L. S. Riza, M. I. Firmansyah, H. Siregar, D. Budiana, and A. Rosales-Pérez, “Determining strategies on playing badminton using the Knuth-Morris-Pratt algorithm,” Telkomnika (Telecommunication Comput. Electron. Control., vol. 16, no. 6, pp. 2763–2770, 2018, doi: 10.12928/TELKOMNIKA.v16i6.11554.

D. Shapira and A. Daptardar, “Adapting the Knuth–Morris–Pratt algorithm for pattern matching in Huffman encoded texts,” Inf. Process. Manag., vol. 42, no. 2, pp. 429–439, 2006, doi: https://doi.org/10.1016/j.ipm.2005.02.003.

U. Ependi and N. Oktaviani, “Abstract Keyword Searching with Knuth Morris Pratt Algorithm,” Sci. J. Informatics, vol. 4, no. 2, pp. 150–157, 2017, doi: 10.15294/sji.v4i2.9797.

P. Gawrychowski, A. Jeż, and Ł. Jeż, “Validating the Knuth-Morris-Pratt Failure Function, Fast and Online,” Theory Comput. Syst., vol. 54, no. 2, pp. 337–372, 2014, doi: 10.1007/s00224-013-9522-8.

L. S. Riza, A. B. Rachmat, Munir, T. Hidayat, and S. Nazir, “Genomic repeat detection using the Knuth-Morris-Pratt algorithm on R high-performance-computing package,” Int. J. Adv. Soft Comput. its Appl., vol. 11, no. 1, pp. 94–111, 2019.


Refbacks

  • There are currently no refbacks.



Barcode

Journal of Applied Data Sciences

2723-6471 (Online)
Organized by : MetaBright
Published by : Bright Publisher
Website : bright-journal.org/JADS
Email : info@bright-journal.org

 This work is licensed under a Creative Commons Attribution-ShareAlike 4.0