For this assignment, you will be implementing the brute force, Knuth-Morris-Pratt, and Boyer-Moore-Horspoole pattern matching algorithms. Each algorithm should return an integer representing the 0-indexed position where a match is found, and -1 if the pattern is not in the string.

The starter code is provided. You have the option of completing the project in C++ . Read the following submission guidelines carefully to ensure that the autograder can properly evaluate your work.

When submitting, zip the exact files listed below for the language you use using the same directory structure,

C++:

In the C++ directory, you will find the following files.

main.cpp *
project2.h *
language.txt *
Makefile *
bmh.cpp
brute.cpp
kmp.cpp

Do not edit the files marked with an asterisk (*), as this could interfere with the autograder. Complete the three files “bmh.cpp”, “brute.cpp”, “kmp.cpp” with the corresponding pattern matching algorithms. To test your code locally, you can use make to build and compile the project, which will generate “project2”. The program will take 3 command line parameters and be run as

$ ./project2 [text string] [pattern string] [algorithm id]

Algorithm id will be one of

• “bmh”: Boyer-Moore-Harspoole
• “kmp”: Knuth-Morris-Pratt
• “brute”: Brute force