STRING MATCHING USING BRUTE FORCE TECHNIQUE
Introduction
In string matching algorithm, we check whether a text T contains a pattern P(length of T>P) i.e to check whether P is a substring of T or not. Since we are trying to check a fixed string P, sometimes these algorithms are called exact string matching algorithms.
In brute force method, for each possible in the text T(length n), we check whether the pattern P(length m) matches or not. We loop from start position of the text T and compare each position of the text with each position of the text. If a mismatch is found then we loop from second position and perform comparisons. It continues until the position n-m of the text.
Working Procedure
Do refer the code available the end of this section to understand the following theory.
- Let m and n be the lengths of pattern P and text T respectively.
-
Loop from i=0 to n-m.
-
Loop from j=0 to m.
- If P[j] == T[i+j] then continue looping. That is if the character in pattern and the character at corresponding position in text are matching correctly, so continue looping.
- Else break the loop, that is a mismatch was found.
- If i==m then the pattern was successfully found at position i;
-
Loop from j=0 to m.
- If you arrived at this step then it means that the pattern wasn't found, so return -1.
Time Complexity: O(n*m)
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for STRING MATCHING USING BRUTE FORCE TECHNIQUEThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!