Implement a Suffix array algorithm in C++
Budget: €30 – €250 EUR
I'm looking for a skilled programmer to help me implement a Suffix array algorithm in C++. The size of the input string is expected to be medium (100-1000 characters). I have specific requirements for the time complexity of the algorithm, and my maximum accepted complexity is O(n log n).
The task is to implement a Suffix array algorithm for exact string matching. I'm given a header file with declared functions that have to be implemented in a separate .cpp file.
construct function - see aufgabe2.hpp, which gets a
suffix array to fill and the text, constructs the suffix array and returns it.
Use the naive construction method with std::sort. Note that a suffix array
never stores strings, only their starting positions in the original text.
The running time of the construction method should therefore be O(n*logn*c), where c is the cost
for comparisons(!) of strings.
Unlike the theoretical tasks, it's not required an extra $ at the end of the
text.
We define that a prefix of a string X is less than X.
In order to use std::sort, you have to create a so-called functor that
< operator defined for 2 text positions or use a lambda function.
find function - Program binary search using the mlr heuristic in. The hits found should be sorted in ascending order by position in the text and be returned.
The task is to implement a Suffix array algorithm for exact string matching. I'm given a header file with declared functions that have to be implemented in a separate .cpp file.
construct function - see aufgabe2.hpp, which gets a
suffix array to fill and the text, constructs the suffix array and returns it.
Use the naive construction method with std::sort. Note that a suffix array
never stores strings, only their starting positions in the original text.
The running time of the construction method should therefore be O(n*logn*c), where c is the cost
for comparisons(!) of strings.
Unlike the theoretical tasks, it's not required an extra $ at the end of the
text.
We define that a prefix of a string X is less than X.
In order to use std::sort, you have to create a so-called functor that
< operator defined for 2 text positions or use a lambda function.
find function - Program binary search using the mlr heuristic in. The hits found should be sorted in ascending order by position in the text and be returned.