CODEWITHSUNDEEP
cstringsearchboyer-moore
H4zy
H4zy

Reputation: 13

Boyer-Moore-Horspool implementation

I wanted to get Boyer-Moore-Horspool implementation for search of some string in text file. Here's my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int bmhSearch(char *needle) {
    FILE *fp;
    int find_result = 0;
    char temp[512];

    size_t nlen = strlen(needle);

    size_t scan = 0;
    size_t bad_char_skip[UCHAR_MAX + 1];
    size_t last;

    if((fopen_s(&fp, "book.txt", "r")) != NULL) {
        return(-1);
    }

    while(fgets(temp, 512, fp) != NULL) {
        size_t hlen = strlen(temp);
        /* pre */
        for (scan = 0; scan <= UCHAR_MAX; scan = scan + 1)
            bad_char_skip[scan] = nlen;
        last = nlen - 1;
        for (scan = 0; scan < last; scan = scan + 1)
            bad_char_skip[needle[scan]] = last - scan;

        while (hlen >= nlen){
            /* scan from the end of the needle */
            char *ptemp = temp;
            for (scan = last; ptemp[scan] == needle[scan]; scan = scan - 1){
                if (scan == 0){
                    find_result++;
                }
            }

            hlen     -= bad_char_skip[ptemp[last]];
            ptemp += bad_char_skip[ptemp[last]];
            printf("%d\t%d\n", hlen, nlen);
        }
    }

    if(fp) {
        fclose(fp);
    }
    return find_result;
}

int main(void){
    char needle[30] = {"some text like this"};
    printf("Matches found: %d\n", bmhSearch(needle);
}

I believe, there is tons of things I did wrong, but I really can't find and fix it. The only thing I've got is on some stage the program doesn't comply with the condition while(hlen >= nlen).

Upvotes: 1

Views: 815

Answers (1)

Mahonri Moriancumer
Mahonri Moriancumer

Reputation: 6003

If the question is "What's wrong with the code?"; here are a few things to start with:

 printf("Matches found: %d\n", bmhSearch(needle); // Missing a final ')'.

 int main(void)
    {
    ...
    return(0);  // Something like this line is required for a function that returns'int'.
    } 

     size_t bad_char_skip[UCHAR_MAX + 1];  // Requires: '#include <limits.h>

     if((fopen_s(&fp, "book.txt", "r")) != NULL) {

The function 'fopen_s()' does not return a pointer. It returns an errno_t type, which is an integer value. Comparing an integer with 'NULL' is like showing up at the 'Indian war-dance' dressed as a cowboy. Perhaps the following is more appropriate:

     if((fopen_s(&fp, "book.txt", "r")) != 0) {

which is equivalent to (my favorite):

     if(fopen_s(&fp, "book.txt", "r")) {

        printf("%d\t%d\n", hlen, nlen);

The above format string is incorrect. it should be:

        printf("%zu\t%zu\n", hlen, nlen);

In a strict C sense, the following lines need attention:

        bad_char_skip[needle[scan]] = last - scan;

        hlen  -= bad_char_skip[ptemp[last]];
        ptemp += bad_char_skip[ptemp[last]];

They should be changed to the following:

        bad_char_skip[(int)needle[scan]] = last - scan;

        hlen  -= bad_char_skip[(int)ptemp[last]];
        ptemp += bad_char_skip[(int)ptemp[last]];

The variable 'ptemp' is defineded as a 'char *'. Hence; 'ptemp[n]' evaluates as a 'char' type; while an array index number must be 'int'.

Upvotes: 1

Related Questions