University of Manchester Pattern Matching Algorithms Java Coding Task

For this assignment, you will be implementing the Rabin-Karp and Bitap 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 either C++ or Java. 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, and upload the zip file to grade scope. For any questions/clarifications, please ask on Ed. 

C++

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

main.cpp *
project3.h *
language.txt *
Makefile *
rk.cpp
bitap.cpp

Do not edit the files marked with an asterisk (*), as this could interfere with the autograder. Complete the two files "rk.cpp" and "bitap.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 "project3". The program will take 3 command line parameters and be run as 

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

Algorithm id will be one of

"bitap": Bitap

“rk”: Rabin-Karp

Java

• In the Java directory, you will find the following files. 
• language.txt *
  project3
  |- Main.java *
  |- Bitap.java
  |- RK.java

Do not edit the files marked with an asterisk (*), as this could interfere with the autograder. Complete the two files “Bitap.java” and “RK.java” by implementing each corresponding algorithm. You can compile and run your program locally using the following commands:

javac project3/*.java
java project3.Main [text string] [pattern string] [algorithm id]

Algorithm id will be one of

“rk”: Rabin-Karp

“bitap”: Knuth-Morris-Prat