Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
Namespaces | |
namespace | cyclic |
namespace | lcs |
namespace | search |
namespace | search_callback |
namespace | suffix_array |
namespace | utils |
Classes | |
class | TestdataFiles |
class | PatternFiles |
This file holds classes caculating longest common subsequence of two sequences.
Implementation of the suffix array search
Time: O(p log n) worst case where p is length of the pattern and n is length of the suffix array
This file holds Rabin-Karp string search algorithm Implementation of the Rabin-Karp algorithm from article Efficient randomized pattern-matching algorithms by Karp, Richard M. and Rabin, Michael O.
This file holds and rolling-hash function implementation used by Rabin-Karp string matching algorithm.
This file contains basic string-search algorithm using suffix arrays
This file holds a checker of suffix array consistency.
The check is based on paper Fast Lightweight Suffix Array Construction and Checking by Stefan Burkhardt and Juha Kärkkäinen
Implementation of suffix array LCP computation in linear time from article [ltLCP] Two space saving tricks for linear time LCP computation by Giovanni Manzini
This file holds implementation to O(n log n) suffix array generation from article Suffix arrays: A new method for on-line string searches by Udi Manber, Gene Myers
Implementation of the suffix array creation by naive sorting method.
Time: O(n^2 log n) worst case when there are suffixes with long same prefixes
Warning: This is only internal testing implementation and running time might be really big. Use other implementations instead.
This file contains testdata filename constants