String Matching Algorithm -A Comparative Survey

String Matching Algorithm -A Comparative Survey

Sushant Pawar, Om Mangle, Burhanuddin Mal, Gaurav Bhaltilak, Jayashree Tamkhade

Department Of Electronics And Telecommunication Engineering,
BRACT’s Vishwakarma Institute Of Information Technology,
Pune, India

Abstract—String matching is a problem with many appli-cations, ranging from simple text processing to complicated bioinformatics and plagiarism detection. This paper surveys four of the string matching algorithms most commonly in use for string matching: Naive, Rabin-Karp, Knuth-MorrisPratt (KMP), and Boyer-Moore. Each of these algorithms uses a different approach to a solution of the described problem. Some algorithms have distinct advantages and difficulties regarding time and space complexity and practical performance.

The naive algorithm is easy to understand but very inefficient for large texts since its time complexity is O(m*n). Rabin-Karp uses hashing in an attempt to speed this up and has an averagecase time complexity of O(m + n) but can be slow as O(m *   n) if hash collisions continually happen. The KMP algorithm develops this further through preprocessing of the pattern to get a constant time complexity of O(m + n) and hence make it very suitable for single-pattern searches. Further optimization is done in the Boyer-Moore algorithm; it scans the pattern from right to left, skips parts of the text, hence achieving the best cases of O(m + n) with worst cases rarely going to O(m * n).

This survey makes a deep analysis and comparative study on these algorithms, focusing on theoretical Aspects, practical implementations, and performance metrics to give an all-rounded insight into these algorithms. Conclusions from the survey will

help choose the best-fit algorithm for an application given a scenario so that the best performance could be achieved considering any string matching scenario.