Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <lcp_naive.h>
Static Public Member Functions | |
template<typename _Iterator , typename _SAIterator > | |
static void | getHeightArray (_Iterator seq_first, _Iterator seq_last, _SAIterator sa_first, _SAIterator sa_last, std::vector< int > *out) |
Static Private Member Functions | |
template<typename _Iterator > | |
static int | lcp (_Iterator pos1, _Iterator pos2, _Iterator last) |
Calculates longest common prefixes of suffix arrays Note: This is trivial naive implementation used mainly for testing. It may have serious performance problems when used with long lcp-s. Use LCPKasai or LCPManzini for real data.
static void strings::suffix_array::LCPNaive::getHeightArray | ( | _Iterator | seq_first, |
_Iterator | seq_last, | ||
_SAIterator | sa_first, | ||
_SAIterator | sa_last, | ||
std::vector< int > * | out | ||
) | [inline, static] |
Calculate "Height array", which is defined as follows height[i] = longest_common_prefix( sequence[pos[k-1]..n), sequence[pos[k]..n)) i.e. it is longest common prefix of two adjacent suffixes (in sorted order).
static int strings::suffix_array::LCPNaive::lcp | ( | _Iterator | pos1, |
_Iterator | pos2, | ||
_Iterator | last | ||
) | [inline, static, private] |