Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
strings::suffix_array::LCPKasai Class Reference

#include <lcp_kasai.h>

List of all members.

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)

Member Function Documentation

template<typename _Iterator , typename _SAIterator >
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]


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines