Algorithms : complete 04-algorithms_on_strings 04-suffix_array

1 files changed, 17 insertions, 7 deletions

diff --git a/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp b/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp
index 13121ae..4ac7afd 100644
--- a/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp
+++ b/04-algorithms_on_strings/04-suffix_array/01-kmp/kmp.cpp
@@ -7,13 +7,23 @@ using std::cin;
 using std::string;
 using std::vector;
 
-// Find all occurrences of the pattern in the text and return a
-// vector with all positions in the text (starting from 0) where 
-// the pattern starts in the text.
-vector<int> find_pattern(const string& pattern, const string& text) {
-  vector<int> result;
-  // Implement this function yourself
-  return result;
+vector<int> find_pattern(const string& pattern, const string& text)
+{
+    vector<int> result;
+    string s = pattern + "$" + text;
+    vector<int> prefixes(s.size());
+    int border = 0;
+    int ps = pattern.size();
+
+    for (int i = 1; i < s.size(); i++) {
+        while ((border > 0) && (s[i] != s[border]))
+            border = prefixes[border - 1];
+        prefixes[i] = border = ((s[i] == s[border]) ? (border + 1) : 0);
+        if (border == ps)
+            result.push_back(i - 2 * ps);
+    }
+
+    return result;
 }
 
 int main() {