Boyer Moore dynamic array implementation

Question

Im trying to implement the Boyer Moore(bad character heuristic) algorithm, except i want to use a dynamic array. Can anyone help me with this problem? here's my source code.

**/* Program for Bad Character Heuristic of Boyer Moore String Matching Algorithm */

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

# define NO_OF_CHARS 256


/* Driver program to test above funtion */
int main()
{
    char txt[];
    char pat[];

    ifstream myfile;
    string filename;

    cout<<"input file"<<endl;
    getline(cin, filename);

    myfile.open(filename.c_str());

        if(myfile.is_open()){
            cout<<"file not found"<<endl;

            while(getline(myfile, txt))
            {
                cout<<txt<<endl;
            }
           cout<<"pls input pattern"<<endl;
           cin.getline(pat[]);
           search(txt, pat);

           myfile.close();

        }
        else cout<<"file not found"<<endl:
    return 0;
}**

well i mean its part of my source code here's the missing part: — Brijinder Singh Mann, Jan 05 '17 at 19:43
My question is how do i implement a Dynamic array into this code? and where do i start? — Brijinder Singh Mann, Jan 05 '17 at 19:46
@BrijinderSinghMann `std::vector` is an implementation of dynamic array. You can start here: http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list — eerorika, Jan 05 '17 at 19:57
As an aside, if you don't want to implement it yourself, it's [already available under ](http://en.cppreference.com/w/cpp/experimental/boyer_moore_searcher) — AndyG, Jan 05 '17 at 20:19

score 0 · Answer 1 · answered Jan 05 '17 at 20:06

0

std::string is exactly what you would need in this case. It is dynamic in size (as in it is sized appropriately when read into). Just be sure to pass the char* pointer part when necessary using the c_str() member function.

answered Jan 05 '17 at 20:06

Kostas

127
5

score 0 · Answer 2 · 2019-12-22T13:15:45.320

I did that like couple of days ago, if you still need the answer... Just declare a dynamic char array and pass it to the function.

Here char str parameter can take a dynamic char array, and with your badchar[NO_OF_CHARS] array you can implement bad character heuristic before you use search function.

void badCharHeuristic(char *str, int badchar[NO_OF_CHARS])
{
    int size = strlen(str);
    int i;

    for (i = 0; i < NO_OF_CHARS; i++)
        badchar[i] = -1;

    for (i = 0; i < size; i++)
        badchar[str[i]] = i;
}

Also your search function should be something like that:

void search(char *txt, char *pat)
{
    int s = 0;  // s is the variable that hold how many shift we are gonna make
    while (s <= (n - m))
    {
        int j = m - 1;

        while (j >= 0 && pat[j] == txt[s + j])
            j--;

        if (j < 0)
        {
            printf("pattern occurs at shift = %d ", s);
            s += (s + m < n) ? m - badchar[txt[s + m]] : 1;  //if s+m < n; s = m - badchar[txt[s + m] else; s = 1
        }
        else
            s += max(1, j - badchar[txt[s + j]]);
    }
}

Hi seaque, welcome. Please consider adding more information. — Tiago Martins Peres, Dec 22 '19 at 12:30

Boyer Moore dynamic array implementation

2 Answers2