Brute force Pattern Matching

A brute force algorithm is a straight forward approach to solving a problem. It also refers to a programming style that does not include any shortcuts to improve performance.

• It is based on trial and error where the programmer tries to merely utilize the computer's fast processing power to solve a problem, rather than applying some advanced algorithms and techniques developed with human intelligence.
• It might increase both space and time complexity.
• A simple example of applying brute force would be linearly searching for an element in an array. When each and every element of an array is compared with the data to be searched, it might be termed as a brute force approach, as it is the most direct and simple way one could think of searching the given data in the array

Brute Force Pattern 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.

function bruteForcePatternMatch(T, P):
    n = length(T)
    m = length(P)

    for i from 0 to n - m:
        j = 0
        while j < m and T[i + j] == P[j]:
            j = j + 1
        if j == m:
            return i  // Pattern found at position i
    return -1  // Pattern not found