Implementations of various search algorithms to detect strings of objects within other strings of objects. More...

Detailed Description

Implementations of various search algorithms to detect strings of objects within other strings of objects.

Collaboration diagram for Search Algorithms:

Files
file	BoyerMoore.h
	Variants of the Boyer-Moore string search algorithm.

Functions
const unsigned int *	vrna_search_BMH_num (const unsigned int needle, size_t needle_size, const unsigned int haystack, size_t haystack_size, size_t start, size_t *badchars, unsigned char cyclic)
	Search for a string of elements in a larger string of elements using the Boyer-Moore-Horspool algorithm. More...

const char *	vrna_search_BMH (const char needle, size_t needle_size, const char haystack, size_t haystack_size, size_t start, size_t *badchars, unsigned char cyclic)
	Search for an ASCII pattern within a larger ASCII string using the Boyer-Moore-Horspool algorithm. More...

size_t *	vrna_search_BM_BCT_num (const unsigned int *pattern, size_t pattern_size, unsigned int num_max)
	Retrieve a Boyer-Moore Bad Character Table for a pattern of elements represented by natural numbers. More...

size_t *	vrna_search_BM_BCT (const char *pattern)
	Retrieve a Boyer-Moore Bad Character Table for a NULL-terminated pattern of ASCII characters. More...

Function Documentation

const unsigned int* vrna_search_BMH_num	(	const unsigned int *	needle,
		size_t	needle_size,
		const unsigned int *	haystack,
		size_t	haystack_size,
		size_t	start,
		size_t *	badchars,
		unsigned char	cyclic
	)

#include <ViennaRNA/search/BoyerMoore.h>

Search for a string of elements in a larger string of elements using the Boyer-Moore-Horspool algorithm.

To speed-up subsequent searches with this function, the Bad Character Table should be precomputed and passed as argument badchars.

See also: vrna_search_BM_BCT_num(), vrna_search_BMH()

Parameters

needle	The pattern of object representations to search for
needle_size	The size (length) of the pattern provided in `needle`
haystack	The string of objects the search will be performed on
haystack_size	The size (length) of the `haystack` string
start	The position within `haystack` where to start the search
badchars	A pre-computed Bad Character Table obtained from vrna_search_BM_BCT_num() (If NULL, a Bad Character Table will be generated automatically)
cyclic	Allow for cyclic matches if non-zero, stop search at end of haystack otherwise

Returns: A pointer to the first occurence of needle within haystack after position start

const char* vrna_search_BMH	(	const char *	needle,
		size_t	needle_size,
		const char *	haystack,
		size_t	haystack_size,
		size_t	start,
		size_t *	badchars,
		unsigned char	cyclic
	)

#include <ViennaRNA/search/BoyerMoore.h>

Search for an ASCII pattern within a larger ASCII string using the Boyer-Moore-Horspool algorithm.

To speed-up subsequent searches with this function, the Bad Character Table should be precomputed and passed as argument badchars. Furthermore, both, the lengths of needle and the length of haystack should be pre-computed and must be passed along with each call.

See also: vrna_search_BM_BCT(), vrna_search_BMH_num()

Parameters

needle	The NULL-terminated ASCII pattern to search for
needle_size	The size (length) of the pattern provided in `needle`
haystack	The NULL-terminated ASCII string of the search will be performed on
haystack_size	The size (length) of the `haystack` string
start	The position within `haystack` where to start the search
badchars	A pre-computed Bad Character Table obtained from vrna_search_BM_BCT() (If NULL, a Bad Character Table will be generated automatically)
cyclic	Allow for cyclic matches if non-zero, stop search at end of haystack otherwise

Returns: A pointer to the first occurence of needle within haystack after position start

size_t* vrna_search_BM_BCT_num	(	const unsigned int *	pattern,
		size_t	pattern_size,
		unsigned int	num_max
	)

#include <ViennaRNA/search/BoyerMoore.h>

Retrieve a Boyer-Moore Bad Character Table for a pattern of elements represented by natural numbers.

Note: We store the maximum number representation of an element num_max at position 0. So the actual bad character table T starts at T[1] for an element represented by number 0.

See also: vrna_search_BMH_num(), vrna_search_BM_BCT()

Parameters

pattern	The pattern of element representations used in the subsequent search
pattern_size	The size (length) of the pattern provided in `pattern`
num_max	The maximum number representation of an element, i.e. the size of the alphabet

Returns: A Bad Character Table for use in our Boyer-Moore search algorithm implementation(s)

size_t* vrna_search_BM_BCT ( const char * pattern )

#include <ViennaRNA/search/BoyerMoore.h>

Retrieve a Boyer-Moore Bad Character Table for a NULL-terminated pattern of ASCII characters.

Note: We store the maximum number representation of an element, i.e. 127 at position 0. So the actual bad character table T starts at T[1] for an element represented by ASCII code 0.

See also: vrna_search_BMH(), vrna_search_BM_BCT_num()

Parameters

pattern The NULL-terminated pattern of ASCII characters used in the subsequent search

Returns: A Bad Character Table for use in our Boyer-Moore search algorithm implementation(s)

Detailed Description

Files

Functions

Function Documentation