Analysis of pattern matching algorithms considering their practical application based on experiments
Vladimir Mikhailov, Tatiana S. Mikhailova, Eldar Miftakhov, Светлана Анатольевна Мустафина · 2022 VIII International Conference on Information Technology and Nanotechnology (ITNT) · 2022
The article presents the results of a study of deterministic algorithms for solving the pattern matching problem: the simplest sequential search algorithm, the Rabin-Karp algorithm, the Knuth-Morris-Pratt algorithm, and the Boyer-Moore algorithm. After analysing the asymptotic complexity indices of the algorithms, a probabilistic search algorithm was constructed and implemented in software. Computational experiments were conducted to simulate the practical application of the considered algorithms. The results of the experiments reflect the methods of application of each algorithm.