dsac::text Namespace Reference

Code from the chapter "Text Processing". More...

Functions
std::vector< std::vector< int > >	lcs (std::string &X, std::string &Y)
	Returns table such that L[j][k] is length of LCS for X[0..j-1] and Y[0..k-1].
std::string	reconstruct_lcs (std::string &X, std::string &Y, const std::vector< std::vector< int > > &L)
	Returns the longest common substring of X and Y, given LCS table L.
std::vector< std::vector< int > >	matrix_chain (const std::vector< int > &d)
int	find_brute (const std::string &text, const std::string &pattern)
	Returns the lowest index at which substring pattern begins in text (or else -1)
int	find_boyer_moore (const std::string &text, const std::string &pattern)
	Returns the lowest index at which substring pattern begins in text (or else -1).
std::vector< int >	compute_kmp_fail (const std::string &pattern)
	Returns the failure table for Knuth, Morris Pratt algorithm.
int	find_kmp (const std::string &text, const std::string &pattern)
	Returns the lowest index at which substring pattern begins in text (or else -1).

Detailed Description

Code from the chapter "Text Processing".

Function Documentation

compute_kmp_fail()

std::vector< int > dsac::text::compute_kmp_fail

(

const std::string &

pattern

)

Returns the failure table for Knuth, Morris Pratt algorithm.

find_boyer_moore()

int dsac::text::find_boyer_moore	(	const std::string &	text,
		const std::string &	pattern
	)

Returns the lowest index at which substring pattern begins in text (or else -1).

find_brute()

int dsac::text::find_brute	(	const std::string &	text,
		const std::string &	pattern
	)

Returns the lowest index at which substring pattern begins in text (or else -1)

find_kmp()

int dsac::text::find_kmp	(	const std::string &	text,
		const std::string &	pattern
	)

Returns the lowest index at which substring pattern begins in text (or else -1).

Here is the call graph for this function:

lcs()

std::vector< std::vector< int > > dsac::text::lcs	(	std::string &	X,
		std::string &	Y
	)

Returns table such that L[j][k] is length of LCS for X[0..j-1] and Y[0..k-1].

matrix_chain()

std::vector< std::vector< int > > dsac::text::matrix_chain

(

const std::vector< int > &

d

)

reconstruct_lcs()

std::string dsac::text::reconstruct_lcs	(	std::string &	X,
		std::string &	Y,
		const std::vector< std::vector< int > > &	L
	)

Returns the longest common substring of X and Y, given LCS table L.