Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
String search algorithms. More...
Functions | |
int | brute_force (const std::string &text, const std::string &pattern) |
std::vector< int > | getFailureArray (const std::string &pattern) |
bool | kmp (const std::string &pattern, const std::string &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) |
String search algorithms.
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.
text | Any string that might contain the pattern. |
pattern | String that we are searching for. |
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
[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 |
true
if pattern was found false
if pattern was not found int64_t string_search::create_hash | ( | const std::string & | s, |
int | n ) |
convert a string to an intger - called as hashing function
[in] | s | source of string to hash |
[in] | n | length of substring to hash |
std::vector< int > string_search::getFailureArray | ( | const std::string & | pattern | ) |
Generate the partial match table aka failure function for a pattern to search.
[in] | pattern | text for which to create the partial match table |
bool string_search::kmp | ( | const std::string & | pattern, |
const std::string & | text ) |
KMP algorithm to find a pattern in a text
[in] | pattern | string pattern to search |
[in] | text | text in which to search |
true
if pattern was found false
if pattern was not found int string_search::rabin_karp | ( | const std::string & | str, |
const std::string & | pat ) |
Perform string pattern search using Rabin-Karp algorithm
[in] | str | string to search in |
[in] | pat | pattern to search for |
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
[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 |