This blog is under construction

Saturday, 25 May 2013

C Program To Implement Brute Force Algorithm

Brute-force search is a problem solving technique which is used to find the solution by systematically enumerating all possible candidates.  For example, it can be used for pattern matching.  Consider an input string "str" and a search string "p".  We will try all possibilities to find whether there's any search string 'p' within the given input string "str". 

See Also:

Example program to implement Brute Force Algorithm:



  #include <stdio.h>
  #include <string.h>
  #define MAX 100

  /* try to find the given pattern in the search string */
  int bruteForce(char *search, char *pattern, int slen, int plen) {
        int i, j, k;

        for (i = 0; i <= slen - plen; i++) {
                for (j = 0, k = i; (search[k] == pattern[j]) &&
                        (j < plen); j++, k++);
                if (j == plen)
                        return j;
        }
        return -1;
  }

  int main() {
        char searchStr[MAX], pattern[MAX];
        int res;
        printf("Enter Search String:");
        fgets(searchStr, MAX, stdin);
        printf("Enter Pattern String:");
        fgets(pattern, MAX, stdin);
        searchStr[strlen(searchStr) - 1] = '\0';
        pattern[strlen(pattern) - 1] = '\0';
        res = bruteForce(searchStr, pattern, strlen(searchStr), strlen(pattern));
        if (res == -1) {
                printf("Search pattern is not available\n");
        } else {
                printf("Search pattern available at the location %d\n", res);
        }
        return 0;
  }



  Output: (Brute Force Search - Example in C)
  jp@jp-VirtualBox:~/$ ./a.out
  Enter Search String:God is Great
  Enter Pattern String:Great
  Search pattern available at the location 5



4 comments:

  1. Good information !!! small correction - on string match it must return i instead of j.

    ReplyDelete
  2. Replies
    1. pattern string length and searched string length

      Delete