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

#include <lcp_naive.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)

Static Private Member Functions

template<typename _Iterator >
static int lcp (_Iterator pos1, _Iterator pos2, _Iterator last)

Detailed Description

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.


Member Function Documentation

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

template<typename _Iterator >
static int strings::suffix_array::LCPNaive::lcp ( _Iterator  pos1,
_Iterator  pos2,
_Iterator  last 
) [inline, static, private]

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