-
Notifications
You must be signed in to change notification settings - Fork 5
Expand file tree
/
Copy pathstring_kmp_std.cpp
More file actions
30 lines (28 loc) 路 964 Bytes
/
Copy pathstring_kmp_std.cpp
File metadata and controls
30 lines (28 loc) 路 964 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// string_prefix_function
template <typename T> vector<int> kmp(const T &text, const T &pattern) {
int n = (int)text.size(), m = (int)pattern.size();
vector<int> lcp = prefix_function(pattern), occurrences;
int matched = 0;
for (int idx = 0; idx < n; ++idx) {
while (matched > 0 && text[idx] != pattern[matched])
matched = lcp[matched - 1];
if (text[idx] == pattern[matched])
matched++;
if (matched == m) {
occurrences.push_back(idx - matched + 1);
matched = lcp[matched - 1];
}
}
return occurrences;
}
template <typename T>
vector<int> search_pattern(const T &text, const T &pattern) {
return kmp(text, pattern);
}
// KMP - Knuth-Morris-Pratt algorithm
// Time Complexity: O(N), Space Complexity: O(N)
// N: Length of text
// Usage:
// string txt = "ABABABAB";
// string pat = "ABA";
// vector<int> ans = search_pattern(txt, pat); {0, 2, 4}