Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <duval.h>
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) |
typedef int strings::cyclic::Duval< T >::SizeType |
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
sequence | |
length |
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
sequence | |
length |
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"
sequence | |
length | length of the sequence |
out | start positions of suffixes of each prefix. For example, out[2] holds starting index of smallest suffix for sequence seq[0],seq[1],seq[2] |