Brute Force Algorithm

If I need to find the string S2 in S1, we will start from first index of s1, iterate (0'th index till N), and compare the characters with the S2. if both not matches, again we will start from the index 1 of s1 (1st index till N). It is a kind of substring search/match problem. 

#include <iostream>
using namespace std;

bool bruteForceAlgo(string s1, string s2) {

    unsigned int longestPrefixMatch = 0;
    for (unsigned int i = 0; i < s1.size(); i++) {
       longestPrefixMatch = 0;
       int iBackup = i;
       for (unsigned int j = 0; j < s2.size(); j++) { 
            if (s1[iBackup] == s2[j]) {
                longestPrefixMatch++;
                /*
                cout << " j " << j << " s1 " << s1[iBackup] << " S2 " << s2[j] << 
                     " Longest Match " << longestPrefixMatch << endl;
                 */
                iBackup++;
            }
            if (longestPrefixMatch == s2.size()) {
                /*
                cout << " j " << j << " s1 " << s1[iBackup] << " S2 " << s2[j] << 
                     " Longest Match " << longestPrefixMatch << endl;
                 */
                return true;
            }
       }
       //cout << " i "  << i  << endl; 
    }

    return false;
}

int main() {
   string s1 = "aaaaaabcd";
   string s2 = "aaaaabc";

   bool matchFound = bruteForceAlgo(s1, s2);
   cout << (matchFound == true ? "Match is Found" : "Match is not found") << endl;;
   return 0;
}

Output:

Match is Found

The worst case is   'consider S1 doesn't have S2 at all, but we don't know. But we will end up going through whole characters of S2 for each S1 index.  O (N*M) where N is the number of characters in the S1 (N = len(S1)), and M is the number of characters in the S2 (M = len(S2)). 

Since we don't want to miss any iteration, we always start from the next index of S1. 

Cons

Bruteforce algorithm is slow as it takes a lot of runtime.

It is inefficient because the time complexity goes beyond O(N!).

It is for smaller problems.