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

#include <binsearch.h>

List of all members.

Static Public Member Functions

template<typename _Iterator , typename _PatternIterator >
static void searchSuffixArray (_Iterator first, _Iterator last, const std::vector< int > &array, _PatternIterator pattern_first, _PatternIterator pattern_last, strings::search_callback::SearchCallback< _Iterator > *callback)

Detailed Description

Implementation of the suffix array search using bin-search algorithm

Time: <it>O(p log n)</it> worst case where p is the length of the pattern and n is the length of the suffix array


Member Function Documentation

template<typename _Iterator , typename _PatternIterator >
static void strings::suffix_array::Binsearch::searchSuffixArray ( _Iterator  first,
_Iterator  last,
const std::vector< int > &  array,
_PatternIterator  pattern_first,
_PatternIterator  pattern_last,
strings::search_callback::SearchCallback< _Iterator > *  callback 
) [inline, static]

Search suffix array and report any matches via #callback

Precondition:
  • <it> [first, last) </it> is valid range
  • <it> [pattern_first, pattern_last) </it> is valid range
  • #array is suffix array of sequence <it> [first, last) </it>
Parameters:
firstpoints to the start of the sequence
lastpoints the the element after the end of the sequence
arraysuffix array corresponding to [first, last)
pattern_firstpoints to the start of the pattern
pattern_lastpoints to the element after the end of the pattern
callbackto be called for each match

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