Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
strings::cyclic::Duval< T > Class Template Reference

#include <duval.h>

List of all members.

Public Types

typedef int SizeType

Static Public Member Functions

static void minimumSuffixes (T *sequence, SizeType length, std::vector< int > *out)
static int leastCyclicShift (T *sequence, int length)
static int leastCyclicShiftEmaxx (T *sequence, int length)

template<typename T>
class strings::cyclic::Duval< T >


Member Typedef Documentation

template<typename T >
typedef int strings::cyclic::Duval< T >::SizeType

Member Function Documentation

template<typename T >
static int strings::cyclic::Duval< T >::leastCyclicShift ( T *  sequence,
int  length 
) [inline, static]

Find lexicographically minimal cyclic shift of the sequence.

This is almost identical to "factor" algorithm 2.1 from article, but we incorporated concatenation(sequence, sequence) into the algorithm instead of explicitly concatening sequences and running original algorithm. The idea is based on the last proposition in the article

Parameters:
sequence
length
Returns:
index of the start of the minimal lexicographic cyclic shift of the sequence. For example result 2 means that smallest shift is sequence(s[2],s[3], ..., s[0],s[1])
template<typename T >
static int strings::cyclic::Duval< T >::leastCyclicShiftEmaxx ( T *  sequence,
int  length 
) [inline, static]

Find lexicographically minimal cyclic shift of the sequence.

This implementation is based on http://e-maxx.ru/algo/duval_algorithm

Parameters:
sequence
length
Returns:
index of the start of the minimal lexicographic cyclic shift of the sequence. For example result 2 means that smallest shift is sequence(s[2],s[3], ..., s[0],s[1])
template<typename T >
static void strings::cyclic::Duval< T >::minimumSuffixes ( T *  sequence,
SizeType  length,
std::vector< int > *  out 
) [inline, static]

Compute lexicographically minimal suffix for each prefix of the input sequence.

Based on pseudocode of algorithm 3.1 from the Duval's article. Note that "end of the string" is smaller than any letter, i.e. "x" < "xa"

Parameters:
sequence
lengthlength of the sequence
outstart positions of suffixes of each prefix. For example, out[2] holds starting index of smallest suffix for sequence seq[0],seq[1],seq[2]

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