Search Algorithms

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

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)
#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.

See also

vrna_search_BMH_num(), vrna_search_BM_BCT()

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.

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.

See also

vrna_search_BMH(), vrna_search_BM_BCT_num()

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.

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)