strings::boyer_moore Namespace Reference

Functions for the Boyer Moore algorithm implementation. More...

Classes
struct	pattern
	A structure representing all the data we need to search the preprocessed pattern in text. More...

Functions
void	init_good_suffix (const std::string &str, std::vector< size_t > &arg)
	A function that preprocess the good suffix thable.
void	init_bad_char (const std::string &str, std::vector< size_t > &arg)
	A function that preprocess the bad char table.
void	init_pattern (const std::string &str, pattern &arg)
	A function that initializes pattern.
std::vector< size_t >	search (const std::string &str, const pattern &arg)
	A function that implements Boyer-Moore's algorithm.
bool	is_prefix (const char *str, const char *pat, size_t len)
	Check if pat is prefix of str.

Detailed Description

Functions for the Boyer Moore algorithm implementation.

Function Documentation

init_bad_char()

void strings::boyer_moore::init_bad_char	(	const std::string &	str,
		std::vector< size_t > &	arg )

A function that preprocess the bad char table.

Parameters

str	The string being preprocessed
arg	The bad char table

Returns

void

Definition at line 138 of file boyer_moore.cpp.

                                                                 {
    arg.resize(APLHABET_SIZE, str.length());
 
    for (size_t i = 0; i < str.length(); i++) {
        arg[str[i]] = str.length() - i - 1;
    }
}

init_good_suffix()

void strings::boyer_moore::init_good_suffix	(	const std::string &	str,
		std::vector< size_t > &	arg )

A function that preprocess the good suffix thable.

Parameters

str	The string being preprocessed
arg	The good suffix table

Returns

void

Definition at line 89 of file boyer_moore.cpp.

                                                                    {
    arg.resize(str.size() + 1, 0);
 
    // border_pos[i] - the index of the longest proper suffix of str[i..] which
    // is also a proper prefix.
    std::vector<size_t> border_pos(str.size() + 1, 0);
 
    size_t current_char = str.length();
 
    size_t border_index = str.length() + 1;
 
    border_pos[current_char] = border_index;
 
    while (current_char > 0) {
        while (border_index <= str.length() &&
               str[current_char - 1] != str[border_index - 1]) {
            if (arg[border_index] == 0) {
                arg[border_index] = border_index - current_char;
            }
 
            border_index = border_pos[border_index];
        }
 
        current_char--;
        border_index--;
        border_pos[current_char] = border_index;
    }
 
    size_t largest_border_index = border_pos[0];
 
    for (size_t i = 0; i < str.size(); i++) {
        if (arg[i] == 0) {
            arg[i] = largest_border_index;
        }
 
        // If we go pass the largest border we find the next one as we iterate
        if (i == largest_border_index) {
            largest_border_index = border_pos[largest_border_index];
        }
    }
}

init_pattern()

void strings::boyer_moore::init_pattern	(	const std::string &	str,
		pattern &	arg )

A function that initializes pattern.

Parameters

str	Text used for initialization
arg	Initialized structure

Returns

void

Definition at line 153 of file boyer_moore.cpp.

                                                      {
    arg.pat = str;
    init_bad_char(str, arg.bad_char);
    init_good_suffix(str, arg.good_suffix);
}

is_prefix()

bool strings::boyer_moore::is_prefix	(	const char *	str,
		const char *	pat,
		size_t	len )

Check if pat is prefix of str.

Parameters

str	pointer to some part of the input text.
pat	the searched pattern.
len	length of the searched pattern

Returns

true if pat IS prefix of str.

false if pat is NOT a prefix of str.

Definition at line 200 of file boyer_moore.cpp.

                                                             {
    if (strlen(str) < len) {
        return false;
    }
 
    for (size_t i = 0; i < len; i++) {
        if (str[i] != pat[i]) {
            return false;
        }
    }
 
    return true;
}

search()

std::vector< size_t > strings::boyer_moore::search	(	const std::string &	str,
		const pattern &	arg )

A function that implements Boyer-Moore's algorithm.

Parameters

str	Text we are seatching in.
arg	pattern structure containing the preprocessed pattern

Returns

Vector of indexes of the occurrences of pattern in text

Definition at line 165 of file boyer_moore.cpp.

                                                                   {
    size_t index_position = arg.pat.size() - 1;
    std::vector<size_t> index_storage;
 
    while (index_position < str.length()) {
        size_t index_string = index_position;
        int index_pattern = static_cast<int>(arg.pat.size()) - 1;
 
        while (index_pattern >= 0 &&
               str[index_string] == arg.pat[index_pattern]) {
            --index_pattern;
            --index_string;
        }
 
        if (index_pattern < 0) {
            index_storage.push_back(index_position - arg.pat.length() + 1);
            index_position += arg.good_suffix[0];
        } else {
            index_position += std::max(arg.bad_char[str[index_string]],
                                       arg.good_suffix[index_pattern + 1]);
        }
    }
 
    return index_storage;
}