Pattern Matching Algorithm In C

Pattern matching techniques are essential in identifying specific patterns within extensive datasets or text. These methods involve comparing a designated pattern with a larger dataset or text to establish its presence. This process is crucial as it enables rapid pattern identification within vast datasets.

Brute Force Pattern Matching Algorithm:

Brute Force Pattern Matching is the simplest Pattern Matching Algorithm. It involves comparing the characters of the pattern with the characters of the text one by one. If all the characters match, the algorithm returns the starting position of the pattern in the text. If not, the algorithm moves to the next position in the text and repeats the comparison until a match is found or the end of the text is reached. The Time Complexity of the Brute Force Algorithm is O(MXN) , where M denotes the length of the text and N denotes the length of the pattern.

Naive Pattern Matching Algorithm:

The Naive Pattern Matching technique represents a step-up from the Brute Force approach as it optimizes the process by bypassing certain text positions, thus avoiding redundant comparisons. It commences the comparison between the pattern and the text from the initial position. Upon finding matching characters, it proceeds to the subsequent position for further evaluation. In instances where the characters do not align, the algorithm shifts to the subsequent text position before reinitiating the comparison. Despite sharing a time complexity of O(MXN) with the Brute Force method, the Naive algorithm typically outperforms it due to its enhanced efficiency.

Knuth-Morris-Pratt Algorithm:

The Knuth-Morris-Pratt (KMP) algorithm represents a sophisticated approach to Pattern Matching. It operates on the principle that leveraging knowledge about the text and pattern during a mismatch can optimize the comparison process. By constructing a table beforehand, the algorithm stores crucial details about the pattern. This table dictates the number of characters in the pattern that can be bypassed upon encountering a mismatch. The Time Complexity of the KMP algorithm is O(M+N).

The Boyer-Moore Algorithm:

One of the widely recognized Pattern Matching techniques is the Boyer-Moore algorithm. Initially introduced in 1977 by Robert S. Boyer and J Strother Moore, this method involves scanning a pattern against a larger dataset or text in a right-to-left manner, distinguishing it from the common left-to-right approach seen in other pattern matching algorithms.

The Boyer-Moore algorithm comprises two primary elements: the negative character rule and the positive suffix rule. The negative character rule functions by scrutinizing the character in the pattern against the corresponding character in the data. Whenever there is a mismatch, the algorithm shifts the pattern to the right until it locates a matching character. On the other hand, the positive suffix rule involves comparing the suffix of the pattern with the corresponding suffix in the data. In case the suffixes are not identical, the algorithm shifts the pattern to the right until a matching suffix is found.

The Boyer-Moore algorithm is recognized for its high performance and is extensively utilized across various applications. It is acknowledged as one of the quickest pattern matching algorithms accessible.

Implementing the Boyer-Moore algorithm in C:

To apply the Boyer-Moore algorithm in C, we initiate by establishing the bad character heuristic. An array can be employed to retain the final appearance of every character within the pattern. This array plays a critical role in deciding the necessary shift to the right for the pattern upon encountering a mismatch.

Here is a demonstration of how we can apply the bad character rule in the C programming language:

C code:

void bad_character_rule(char *pattern, int pattern_length, int *bad_char)
{
   int i;
   for (i = 0; i < NO_OF_CHARS; i++)
      bad_char[i] = -1;
   for (i = 0; i < pattern_length; i++)
      bad_char[(int) pattern[i]] = i;
}

In this instance, we start by setting all characters in the array to -1. Subsequently, we proceed to loop through the pattern and modify the array to store the index of the last occurrence of each character in the pattern.

Next, we will proceed with integrating the effective suffix rule. We can employ an array to retain the size of the longest suffix of the pattern that aligns with a suffix of the data or text. This array will assist us in deciding the necessary rightward shift for the pattern.