ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT
  • 450 DSA Cracker
  • 5G NR
  • O-RAN

Introduction to Brute force approach with example

prodevelopertutorial August 18, 2019

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:

 

Introduction to Brute force approach with example

 

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.

 

Introduction to Brute force approach with example

 

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.

 

Introduction to Brute force approach with example

 

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

 

Introduction to Brute force approach with example

 

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+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Follow this blog to learn more about C, C++, Linux, Competitive Programming concepts, Data Structures.

Leave a Reply Cancel Reply

You must be logged in to post a comment.

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2023 ProDeveloperTutorial.com
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept”, you consent to the use of ALL the cookies.
Do not sell my personal information.
Cookie SettingsAccept
Manage consent

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. These cookies ensure basic functionalities and security features of the website, anonymously.
CookieDurationDescription
cookielawinfo-checkbox-analytics11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checkbox-functional11 monthsThe cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checkbox-necessary11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-others11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-performance11 monthsThis cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy11 monthsThe cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.
Functional
Functional cookies help to perform certain functionalities like sharing the content of the website on social media platforms, collect feedbacks, and other third-party features.
Performance
Performance cookies are used to understand and analyze the key performance indexes of the website which helps in delivering a better user experience for the visitors.
Analytics
Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics the number of visitors, bounce rate, traffic source, etc.
Advertisement
Advertisement cookies are used to provide visitors with relevant ads and marketing campaigns. These cookies track visitors across websites and collect information to provide customized ads.
Others
Other uncategorized cookies are those that are being analyzed and have not been classified into a category as yet.
SAVE & ACCEPT