Assignment 2 [10 marks]
Deadline: Your lab in the week starting at 14 Dec 2024

This assignment is individual, each student must write his own code.
You are not allowed to copy any piece of code from the internet or from any other resource.
You are not allowed to copy any piece of code from other students.
You are allowed to make a partial implementation for a partial mark.

Implement a Suffix Array prefix doubling construction algorithm with time O(n (log n)^2) and memory space O(n) as described in our lecture.
Do not use string class, use char arrays. The memory space used by algorithm must not exceed O(n) at any time during execution.
Your code must be general to handle any string or query.
Use standard C++, such that the following main() works. You are not allowed to modify the main().
You are not allowed to include any files or built-in libraries, except for output.

int main()
{
    SuffixArray t("ACGACTACGATAAC$");

    t.ConstructUsingPrefixDoubling();

    t.Print(); // Prints:  14 11 12  0  6  3  9 13  1  7  4  2  8 10  5

    return 0;
}

// The following is just illustration for your help only, nothing required about it. Check lecture.
///////////////////////////////////////////////////////////////////////////////////////////////////
// i      0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
// t      A  C  G  A  C  T  A  C  G  A  T  A  A  C  $
// --------------------------------------------------
// k=0    1  2  3  1  2  4  1  2  3  1  4  1  1  2  0
// k=1    2  5  7  2  6  8  2  5  7  3  8  1  2  4  0
// k=2    3  7 10  4  9 13  3  8 11  5 12  1  2  6  0
// k=4    3  8 11  5 10 14  4  9 12  6 13  1  2  7  0
// sa=   14 11 12  0  6  3  9 13  1  7  4  2  8 10  5
///////////////////////////////////////////////////////////////////////////////////////////////////