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

#include <lcs.h>

List of all members.

Static Public Member Functions

static int length (const T *seq1, int len1, const T *seq2, int len2)
static int subsequence (const T *seq1, int len1, const T *seq2, int len2, std::vector< T > *out)

Detailed Description

template<typename T>
class strings::lcs::LCS< T >

Trivial dynamic programming computation of LCS


Member Function Documentation

template<typename T >
static int strings::lcs::LCS< T >::length ( const T *  seq1,
int  len1,
const T *  seq2,
int  len2 
) [inline, static]

Compute the length of the longest common subsequence of two sequences.

Running time is O(nm) , memory is O(n+m)

Returns:
LCS length
template<typename T >
static int strings::lcs::LCS< T >::subsequence ( const T *  seq1,
int  len1,
const T *  seq2,
int  len2,
std::vector< T > *  out 
) [inline, static]

Computes the longest common subsequence of two sequences.

Running time O(nm) , memory O(nm)

See also:
length() if you only need length of the LCS
Parameters:
outLCS will be written here
Returns:
length of the LCS

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