String Matching Algorithm is a method to identify certain patterns or occurrences in a bigger text or string. There are various algorithms purposely made for it to check the effectiveness based on the nature of the problem. The most commonly used string-matching algorithms are mentioned below -
Brute Force - Brute force is one of the simplest methods of string matching algorithms. Under this, every possible position of the text is checked to get an exact match with the pattern. Its time complexity is determined by the equation O (n - m + 1) where n stands for the length of the text and m is for the length of the pattern.
Knuth-Morris-Pratt (KMP) Algorithm - Knuth-Morris-Pratt (KMP) Algorithm is an effective method for preprocessing patterns that enables the pattern to skip characters in the text based on prior matches by producing a "partial match" table (also called the prefix function or pi function). As a consequence, the time complexity of O (n + m).
| Commonly Used String Matching Algorithm | |
| Brute Force | Finite Automation Algorithm |
| Rabin-Karp Algorithm | Boyer-Moore Algorithm |
| Knoth-Morris-Pratt (KMP) Algorithm | Suffix Trees and Arrays |
Boyer-Moore Algorithm - Boyer Moore is another algorithm that allows the skipping of texts based on character comparisons by preprocessing the pattern. It results in good performance when practiced with an average case time complexity of O (n + m).
Rabin-Karp Algorithm - Rabin-Karp algorithm is the kind of algorithm that uses hashing to find matches. For the pattern, it brings hash values and substrings of the text and makes a competitive analysis to find relevant matches. Its average time complexity is O (n + m). However, its worst case complexity can be higher.
Finite Automation Algorithm - Finite automation algorithm is actually a theoretical machines that processes both text and pattern simultaneously, enabling for fast matching with a linear time complexity. However, preprocessing of the pattern is needed.
Suffix Trees and Arrays - Data structures that can be used to quickly search for patterns by preprocessing the text. Although they are more difficult to construct, they have incredibly quick search speeds.
Conclusion
The algorithm to be chosen depends on multiple factors like the size of the text and pattern, in which the frequency of pattern changes, the necessity for preprocessing time, and the efficiency of search time. Since every algorithm has pros and cons, they can be applied to various string-matching task conditions.
