Evaluation of the Boyer-Moore and Knuth-Morris-Pratt String-Searching

The utilization of string searching algorithms holds significant importance within the field of computer science, including applications in diverse areas such as text pro- cessing and data analysis. With the advancement of technology, we strive to opti- mize our search methods for text, whether it is for words, or phrases. Therefore, the choice of algorithm used to search for a specific string becomes crucial in achiev- ing the fastest possible results. While many studies have compared string searching algorithms, limited work has explored how various factors influence their perfor- mance, particularly in terms of execution time. Accordingly, this work aims to in- vestigate and evaluate the performance of commonly used string searching algo- rithms, namely Boyer-Moore, and Knuth-Morris-Pratt, under varying conditions such as text size, pattern length, RAM, CPU, and choice of compiler. The work in- volves also a comparative analysis of their performance using the java programming language with two different IDEs compilers, namely the NetBeans JDK and ECJ compiler as well as different RAM and CPU configurations. To determine the im- pact of these factors on the efficiency of the two algorithms, we use factorial analy- sis, which enables us to assess the relative importance of each factor and identify their interactions. This work bridges the gap in existing work by investigating how these factors impact the execution time of string searching algorithms. The analysis provides valuable insights into the strength and limitations of different algorithms, offering guidance for optimizing their use and contributing to the development of more efficient solutions for string searching tasks. In summary, the findings indicate that the text size and compiler choice have a significant influence on the execution times of the Boyer-Moore (BM) and Knuth-Morris-Pratt (KMP), algorithms, with text size having the greatest impact on the execution time.