COMPARATIVE ANALYSIS OF TIME EFFICIENCY OF SUBSTRING SEARCH ALGORITHMS
DOI:
https://doi.org/10.34185/1991-7848.itmm.2025.01.045Keywords:
information technology, machine-based benchmarking, S- and R-metrics, substring search algorithm, time efficiency of algorithms.Abstract
This paper presents a comparative analysis of the time efficiency of four classical string searching algorithms that attempt to identify the position where one or more pattern strings occur within a longer string or text. The evaluated algorithms include the naive (brute-force) method, Knuth–Morris–Pratt (KMP), Boyer–Moore, and Rabin–Karp. The experiments were conducted on three different processor architectures using three datasets of varying sizes. Each algorithm was tested under both cold and warm cache conditions. To reduce external influence, the benchmarking was limited to a single CPU core, and memory was forcibly cleaned after each run. The experimental results were analyzed using S- and R-indicators of efficiency, and practical recommendations are provided regarding the applicability of each algorithm under different operating conditions.
References
Shynkarenko V. I. Comparative Analysis of Time Efficiency of Functionally Equivalent Algorithms. Problems of Programming, 2001, Vol. 3–4, pp. 31–39.
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. MIT Press. – 2009. 1292 p.
Knuth D.E., Morris J.H., Pratt V.R. Fast Pattern Matching in Strings. SIAM Journal on Computing. – 1977. Vol. 6(2). P. 323–350.
Boyer R. S., Moore J. S. A Fast String Searching Algorithm. Communications of the ACM. – 1977. Vol. 20(10). P. 762–772.
Karp R. M., Rabin M. O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. – 1987. Vol. 31(2). P. 249–260.
