String search algorithms.
More...
|
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) |
|
String search algorithms.
for assert for IO operations for std::string for std::vector
◆ brute_force()
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.
21 {
22 size_t pat_l = pattern.
length();
23 size_t txt_l = text.
length();
24 int index = -1;
25 if (pat_l <= txt_l) {
26 for (size_t i = 0; i < txt_l - pat_l + 1; i++) {
28 if (s == pattern) {
29 index = i;
30 break;
31 }
32 }
33 }
34 return index;
35}
◆ 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?
61 {
62 if (end1 - start1 != end2 - start2) {
63 return false;
64 }
65 while (start1 <= end1 && start2 <= end2) {
66 if (str1[start1] != str2[start2]) {
67 return false;
68 }
69 start1++;
70 start2++;
71 }
72 return true;
73}
◆ 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
25 {
26 int64_t result = 0;
27 for (int i = 0; i < n; ++i) {
28 result += (int64_t)(s[i] * (int64_t)pow(
PRIME, i));
29 }
30 return result;
31}
#define PRIME
Prime modulus for hash functions.
Definition rabin_karp.cpp:16
◆ getFailureArray()
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
32 {
33 size_t pattern_length = pattern.
size();
35 failure[0] = std::string::npos;
36 size_t j = std::string::npos;
37 for (int i = 0; i < pattern_length; i++) {
38 while (j != std::string::npos && pattern[j] != pattern[i]) {
39 j = failure[j];
40 }
41 failure[i + 1] = ++j;
42 }
43 return failure;
44}
◆ kmp()
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
53 {
54 if (pattern.
empty()) {
55 return 0;
56 }
58 size_t text_length = text.
size();
59 size_t pattern_length = pattern.
size();
60 size_t k = 0;
61 for (size_t j = 0; j < text_length; j++) {
62 while (k != std::string::npos && pattern[k] != text[j]) {
63 k = failure[k];
64 }
65 if (++k == pattern_length) {
67 }
68 }
69 return std::string::npos;
70}
double k(double x)
Another test function.
Definition composite_simpson_rule.cpp:117
◆ rabin_karp()
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
83 {
86 for (
int i = 0; i <= str.
size() - pat.
size(); ++i) {
87 if (pat_hash == str_hash &&
90 return i;
91 }
93 str_hash =
94 recalculate_hash(str, i, i + pat.
size(), str_hash, pat.
size());
95 }
96 }
97 return -1;
98}
int64_t create_hash(const std::string &s, int n)
Definition rabin_karp.cpp:25
bool check_if_equal(const std::string &str1, const std::string &str2, int start1, int end1, int start2, int end2)
Definition rabin_karp.cpp:60
◆ 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
43 {
44 int64_t new_hash = old_hash - s[old_index];
46 new_hash += (int64_t)(s[new_index] * (int64_t)pow(
PRIME, patLength - 1));
47 return new_hash;
48}