Explain Brute Force String matching problem with an example Write an algorithm for same and analyze its efficiency.

In this post we are discussing about Explain Brute Force String matching problem with an example Write an algorithm for same and analyze its efficiency.

The Brute Force String Matching problem is a simple but naive approach to find all occurrences of a pattern (substring) within a text (string). The idea is to compare the pattern with every possible substring of the text to check for a match. While this algorithm is straightforward, it is not the most efficient method for large texts or patterns.

Here’s how the Brute Force String Matching problem works with an example:

Example:
Suppose we want to find all occurrences of the

Text: “HELLOGEM”
Pattern: “GEM”

Brute Force String Matching Algorithm:

1. Start at the beginning of the text and slide the pattern window over it.
2. At each position of the text, compare the characters in the pattern with the characters in the text.
3. If a mismatch is found, move the pattern window one position to the right in the text.
4. Repeat steps 2 and 3 until the pattern window reaches the end of the text.
5. If a match is found (all characters in the pattern match the corresponding characters in the text), record the starting position of the match.
6. Move the pattern window one position to the right in the text and repeat steps 2-5.
7. Continue this process until the pattern window reaches the end of the text.

Algorithm for Brute Force String Matching:

Algo StringMatching(T[0 . . . n-1], P[0 . . . m-1])
{
    for i <- 0 to n-m do
    {
        j <- 0; // Initialize j inside the outer loop
        while j < m and p[j] = T[i+j] do
        {
            j <- j+1;
        }
        if j = m
        {
            return i; // Pattern found at position i
        }
    }
    return -1; // Pattern not found
}

Efficiency Analysis:

The efficiency of the Brute Force String Matching algorithm depends on the lengths of the text and pattern:

• Time Complexity: In the worst case, the algorithm may have to compare the pattern with all possible substrings of the text, resulting in O(n * m) comparisons, where ‘n’ is the length of the text and ‘m’ is the length of the pattern. This is the worst-case time complexity.
• Best Case: The best-case scenario occurs when the pattern doesn’t occur in the text at all. In this case, the algorithm performs a single pass through the text, making ‘n’ comparisons. The best-case time complexity is O(n).
• Average Case: The average-case time complexity is also O(n * m) on average, as it depends on the distribution of patterns in the text.
• Space Complexity: The space complexity is O(1), as the algorithm only requires a constant amount of extra memory for variables to keep track of the positions in the text and pattern.