Home / Featured / Brute Force algorithm

Brute Force algorithm

The brute force algorithm (also known as brute force search) consists in checking, at all positions in the text between 0 and nm, whether an occurrence of the pattern starts there or not. Then, after each attempt, it shifts the pattern by exactly one position to the right. This technique is very commonly used technique for problem solving in C++.

The brute force algorithm requires no preprocessing phase, and a constant extra space in addition to the pattern and the text. During the searching phase the text character comparisons can be done in any order. The time complexity of this searching phase is O(mn) (when searching for am-1b in an for instance). The expected number of text character comparisons is 2n.

The C code

void BF(char *x, int m, char *y, int n) {
   int i, j;

   /* Searching */
   for (j = 0; j <= n - m; ++j) {
      for (i = 0; i < m && x[i] == y[i + j]; ++i);
      if (i >= m)
         OUTPUT(j);
   }
}
   

This algorithm can be rewriting to give a more efficient algorithm in practice as follows:

#define EOS '\0'
   
void BF(char *x, int m, char *y, int n) { 
  char *yb; 
  /* Searching */ 
  for (yb = y; *y != EOS; ++y) 
    if (memcmp(x, y, m) == 0) 
      OUTPUT(y - yb);
}

About Raj Maurya

Check Also

xiaomi mi6

Utility of Modern Cell Phones

One can make a considerable amount of savings by purchasing wholesale cell phones in the …

Leave a Reply

Your email address will not be published. Required fields are marked *