Introduction to Brute force approach with example

Brute force approach can also be called as exhaustive search. Basically brute force means you go through all the possible solutions.

It is one of the easiest way to solve a problem. But in terms of time and space complexity will take a hit.

So let’s understand brute force approach with help of example.

 

 

Problem statement:

 

You are given a string “s” and s pattern “p”, you need to check if the pattern is there in the string.

S = “prodevelopertutorial”

P = “rial”

 

We need to check if “rial” is present in “prodevelopertutorial” string.

 

We shall use brute force approach to solve this problem.

 

In this approach, we try to match character by character. If there is a mismatch, we start the search again from the next character of the string. The algorithm can be visualized as below:

 

 

Here the first character of the string and first character of the pattern is a mismatch.  Hence we move to next character and check again.

 

 

If you can see from the above image, the first character is a match in both of the strings, hence we move to the next character. Here the next character is a mismatch. Hence we shift the search string to the next character.

 

 

Again there is a mismatch. Again we move to next character. We continue this till me find the pattern or reach end of the string

 

 

Here we have found our substring, hence we exit the loop.

As you can see above, when there is a mismatch we jump character by character. Hence the time complexity will be n*m, where “n” is the length of the string “s” and “m” is the length if the pattern “p” at the worst case.

 

C++ program to for sub string search using brute force approach.

 

#include<iostream>
#include<string>

using namespace std;

bool search(string str, string pattern)
{   
	int n = str.length();  
	int m = pattern.length();   
 
	for (int i = 0; i <= n - m; i++)   
	{         
		int j;      
		for (j = 0; j < m; j++)
		{        
			if (str[i+j] != pattern[j])            
				break; 
		}  
		if (j == m) 
			return true;   
	}   
		return false;
}

int main()
{
	string str = "prodevelopertutrial";
	string pattern = "rial";

	if(search(str, pattern))
	{
		cout<<"The substring is present"<<endl;
	}
	else
	{
		cout<<"The substring is NOT present"<<endl;		
	}

	return 0;
}

 

Output:

 

The substring is present.

 

 

Some of the examples of brute force approach are:

1. Sequential search
2. String matching algorithm
3. Travelling sales man problem
4. Knapsack problem

We shall study the above problems in later chapter.

 

For Travelling sales man problem and Knapsack problem, there is no polynomial time solution. Hence they are classified as NP hard problem. But they can solved by using backtracking approach, that will increase the efficiency of the algorithm.

 

For the above sub string search problem, is there a way to increase the efficiency?

 

Yes, efficiency can be increased by using below algorithms.

 

1. KMP algorithm
2. Rabir Karp Algorithm
3. Boyer Moore Algorithm.

 

We shall also study about these algorithms in further chapter.

Further Reading:

AJ’s definitive guide for DS and Algorithms. Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.

 

List Of Tutorials available in this website:

C Programming 20+ Chapters	C++ Programming 80+ Chapters
100+ Solved Coding Questions	Data Structures and Algorithms 85+ Chapters
System design 20+ Chapters	Shell Scripting 12 Chapters
4g LTE 60+ Chapters	Most Frequently asked Coding questions
5G NR 50+ Chapters	Linux System Programming 20+ chapters