Performance and Implementation Comparison of Knuth-Morris-Pratt and Boyer-Moore String Search Algorithms

Saleh T., CORUT ERGİN F., Malkawi M., Alhajj R.

2nd International Conference on Advanced Innovations in Smart Cities, ICAISC 2025, Jeddah, Suudi Arabistan, 9 - 11 Şubat 2025, (Tam Metin Bildiri) identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1109/icaisc64594.2025.10959692
  • Basıldığı Şehir: Jeddah
  • Basıldığı Ülke: Suudi Arabistan
  • Anahtar Kelimeler: Boyer-Moore algorithm, KMP algorithm, Knuth-Morris-Pratt algorithm, Pattern matching, String matching, String search algorithms
  • Marmara Üniversitesi Adresli: Evet

Özet

String search algorithms play an important role in many research areas such as data mining and bioinformatics. While there exist a number of algorithms that handles the topic, we are exploring the the Knuth-Morris-Pratt (KMP) and Boyer-Moore algorithms due to their efficiency and versatility. In this work, we compared the algorithms in terms of characteristics, performance and implementation details. We also tested both the algorithms with various patterns and texts that differs in size. We also analyzed the performance of the algorithms on 4 different processors to understand the technological advancements effects on their performance. Our findings suggest that the BM algorithm perform better with large texts and patterns, while the KMP algorithm is better suited for smaller ones. Also, while newer processor generally exhibit improved performance, the significance of these enhancements may vary. Thus, we should rather be looking specific architectural advancements within generations rather than focusing solely on the generational gap.