Task: Edit SuffixArray.cpp

In this part of the assignment, we have provided a file called SuffixArray.cpp that contains initial steps towards implementing a Suffix Array. Function headers (with usage details) are included in SuffixArray.h. Your task is to fill in the missing code.

Remember that, in the naive algorithm to construct a Suffix Array from a given string s of length n, you will likely be doing the following tasks:

Create a vector<int> containing the integers 0, 1, …, n|/p>

Sort the vector<int> such that, when you compare two integers i and j, instead of comparing their actual values, you compare the suffixes of s that start at indices i and j, respectively

For example, if s is DOG, if you are comparing the integers 1 and 2, 1 would be greater than 2 because the suffix of s starting at index 1 (OG)  is alphabetically larger than the suffix of s starting at index 2 (G)

Hint: You will want to define a custom comparison function that, when given two integers i and j, compares the suffixes of s starting at indices i and j. Refer to the C++ sort documentation to see an example of the syntax of defining and using a custom comparison function.

Compiling and Running

We have provided a tester program, SuffixArrayTest, that will help you test your code. You can compile your code using the provided Makefile via the make command:

$ make g++ -Wall -pedantic -g -O0 -std=c++11 -o SuffixArrayTest SuffixArrayTest.cpp SuffixArray.cpp 

If you want to clean up your environment by deleting all the compiled executables, you can simply run make clean:

$ make clean rm -f SuffixArrayTest *.o 

When run, SuffixArrayTest will ask the user to input a string, and it will print the Suffix Array of the user-inputted string. You can assume the string will be in the alphabet {A½. Here’s an example of how it should look like when it’s run from the command line:

$ ./SuffixArrayTest Enter a string: DOG  0 2 1

Task: Edit BWT.cpp

1. In this part of the assignment, we have provided a file called BWT.cpp that contains initial steps towards implementing the Burrows-Wheeler Transform. Function headers (with usage details) are included in BWT.h. Your task is to fill in the missing code.

Hint: The code you wrote to implement the Suffix Array can likely be adapted to implement the BWT in this challenge.

Compiling and Running

We have provided a tester program, BWTTest, that will help you test your code. You can compile your code using the provided Makefile via the make command:

1. $ make g++ -Wall -pedantic -g -O0 -std=c++11 -o BWTTest BWTTest.cpp BWT.cpp 

If you want to clean up your environment by deleting all the compiled executables, you can simply run make clean:

$ make clean rm -f BWTTest *.o 

When run, BWTTest will ask the user to input a string (including end-of-string symbol, $), and it will print the Burrows-Wheeler Transform of the user-inputted string. You can assume the string will be in the alphabet {A½. Here’s an example of how it should look like when it’s run from the command line:

$ ./BWTTest Enter a string: BANANA$  ANNB$AA