Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <lcp_kasai.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 void strings::suffix_array::LCPKasai::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).
Rank is inverse array to pos, i.e. rank[pos[i]]=i. This actually means, that if we sort suffixes, the i-th position in the sorted array will belong to suffix starting at rank[i]