string_search Namespace Reference

String search algorithms. More...

Functions
int	brute_force (const std::string &text, const std::string &pattern)
std::vector< size_t >	getFailureArray (const std::string &pattern)
	Generate the partial match table aka failure function for a pattern to search.
size_t	kmp (const std::string &pattern, const std::string &text)
	KMP algorithm to find a pattern in a text.
int64_t	create_hash (const std::string &s, int n)
int64_t	recalculate_hash (const std::string &s, int old_index, int new_index, int64_t old_hash, int patLength)
bool	check_if_equal (const std::string &str1, const std::string &str2, int start1, int end1, int start2, int end2)
int	rabin_karp (const std::string &str, const std::string &pat)

Detailed Description

String search algorithms.

for assert for IO operations for std::string for std::vector

Function Documentation

brute_force()

int string_search::brute_force	(	const std::string &	text,
		const std::string &	pattern )

Find a pattern in a string by comparing the pattern to every substring.

Parameters

text	Any string that might contain the pattern.
pattern	String that we are searching for.

Returns

Index where the pattern starts in the text

-1 if the pattern was not found.

Definition at line 21 of file brute_force_string_searching.cpp.

                                                                 {
    size_t pat_l = pattern.length();
    size_t txt_l = text.length();
    int index = -1;
    if (pat_l <= txt_l) {
        for (size_t i = 0; i < txt_l - pat_l + 1; i++) {
            std::string s = text.substr(i, pat_l);
            if (s == pattern) {
                index = i;
                break;
            }
        }
    }
    return index;
}

check_if_equal()

bool string_search::check_if_equal	(	const std::string &	str1,
		const std::string &	str2,
		int	start1,
		int	end1,
		int	start2,
		int	end2 )

compare if two sub-strings are equal

Parameters

[in]	str1	string pattern to search
[in]	str2	text in which to search
[in]	start1,end1	start and end indices for substring in str1
[in]	start2,end2	start and end indices for substring in str2

Returns

true if pattern was found

false if pattern was not found

Note

can this be replaced by std::string::compare?

Definition at line 60 of file rabin_karp.cpp.

                                                                {
    if (end1 - start1 != end2 - start2) {
        return false;
    }
    while (start1 <= end1 && start2 <= end2) {
        if (str1[start1] != str2[start2]) {
            return false;
        }
        start1++;
        start2++;
    }
    return true;
}

create_hash()

int64_t string_search::create_hash	(	const std::string &	s,
		int	n )

convert a string to an intger - called as hashing function

Parameters

[in]	s	source of string to hash
[in]	n	length of substring to hash

Returns

hash integer

Definition at line 25 of file rabin_karp.cpp.

                                               {
    int64_t result = 0;
    for (int i = 0; i < n; ++i) {
        result += (int64_t)(s[i] * (int64_t)pow(PRIME, i));
    }
    return result;
}

getFailureArray()

std::vector< size_t > string_search::getFailureArray

(

const std::string &

pattern

)

Generate the partial match table aka failure function for a pattern to search.

Parameters

pattern

text for which to create the partial match table

Returns

the partial match table as a vector array

Definition at line 32 of file knuth_morris_pratt.cpp.

                                                            {
    size_t pattern_length = pattern.size();
    std::vector<size_t> failure(pattern_length + 1);
    failure[0] = std::string::npos;
    size_t j = std::string::npos;
    for (int i = 0; i < pattern_length; i++) {
        while (j != std::string::npos && pattern[j] != pattern[i]) {
            j = failure[j];
        }
        failure[i + 1] = ++j;
    }
    return failure;
}

kmp()

size_t string_search::kmp	(	const std::string &	pattern,
		const std::string &	text )

KMP algorithm to find a pattern in a text.

Parameters

pattern	string pattern to search
text	text in which to search

Returns

the starting index of the pattern if found

std::string::npos if not found

Definition at line 53 of file knuth_morris_pratt.cpp.

                                                            {
    if (pattern.empty()) {
        return 0;
    }
    std::vector<size_t> failure = getFailureArray(pattern);
    size_t text_length = text.size();
    size_t pattern_length = pattern.size();
    size_t k = 0;
    for (size_t j = 0; j < text_length; j++) {
        while (k != std::string::npos && pattern[k] != text[j]) {
            k = failure[k];
        }
        if (++k == pattern_length) {
            return j - k + 1;
        }
    }
    return std::string::npos;
}

rabin_karp()

int string_search::rabin_karp	(	const std::string &	str,
		const std::string &	pat )

Perform string pattern search using Rabin-Karp algorithm

Parameters

[in]	str	string to search in
[in]	pat	pattern to search for

Returns

index of first occurrence of pattern

-1 if pattern not found

Definition at line 83 of file rabin_karp.cpp.

                                                           {
    int64_t pat_hash = create_hash(pat, pat.size());
    int64_t str_hash = create_hash(str, pat.size());
    for (int i = 0; i <= str.size() - pat.size(); ++i) {
        if (pat_hash == str_hash &&
            check_if_equal(str, pat, i, i + pat.size() - 1, 0,
                           pat.size() - 1)) {
            return i;
        }
        if (i < str.size() - pat.size()) {
            str_hash =
                recalculate_hash(str, i, i + pat.size(), str_hash, pat.size());
        }
    }
    return -1;  // return -1 if given pattern not found
}

recalculate_hash()

int64_t string_search::recalculate_hash	(	const std::string &	s,
		int	old_index,
		int	new_index,
		int64_t	old_hash,
		int	patLength )

re-hash a string using known existing hash

Parameters

[in]	s	source of string to hash
[in]	old_index	previous index of string
[in]	new_index	new index of string
[in]	old_hash	previous hash of substring
[in]	patLength	length of substring to hash

Returns

new hash integer

Definition at line 42 of file rabin_karp.cpp.

                                                          {
    int64_t new_hash = old_hash - s[old_index];
    new_hash /= PRIME;
    new_hash += (int64_t)(s[new_index] * (int64_t)pow(PRIME, patLength - 1));
    return new_hash;
}