Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
strings Namespace Reference

Namespaces

namespace  cyclic
namespace  lcs
namespace  search
namespace  search_callback
namespace  suffix_array
namespace  utils

Classes

class  TestdataFiles
class  PatternFiles

Detailed Description

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

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines