**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:**

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