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:

1. 
   

   
   Create a
   vector
   containing the integers 0, 1, ...,
   n–1
   

   
   


2. 
   

   
   Sort the
   vector
   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
     NIEMA, if you are comparing the integers 1 and 2, 1 would be greater than 2 because the suffix of
     s
     starting at index 1 (IEMA) is alphabetically larger than the suffix of
     s
     starting at index 2 (EMA)
     

     
     
   
   
   
   

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.

Part 3.2: Burrows-Wheeler Transform Coding