COMPARATIVE ANALYSIS OF TIME EFFICIENCY OF SUBSTRING SEARCH ALGORITHMS

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.