String Matching Algorithms :: Naive Bruteforce

In this blog series, I will try to explain and evaluate various string matching algorithms.

1. Bruteforce Algorithm
2. Rabin Karp Fingerprinting Algorithm
3. Knuth Morris Pratt Algorithm
4. Bayer-Moore Algorithm
5. Bruteforce Algorithm:

Bruteforce is the most basic string matching algorithm there is out there. For a string ‘s’ with length ‘m’ and pattern ‘t’ with length ’n’, bruteforce works in the following way:

Take a string s[0…m] and a pattern t[0…n]. For a loop counter ‘i’ going from 0 to m, check for the correctness of characters s[i] and t[0]. If the characters match, then the remaining characters of the pattern are also matched. Otherwise, i is incremented and next character position is checked.

Code:

The code checks for the first character. If it is matched, it proceeds and finds the first position of the pattern to be searched. Otherwise, it quits the program. As you run the program, you can see that a character match can be found at position 12 but it is not an accurate one. Another first character match is found at position 16, and it is the correct answer.

Time Complexity: O(mn)