From 52041be8af3d321f07feb27fbba70b364d72c10a Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Mon, 14 Nov 2016 07:01:13 +0100 Subject: Algorithms : complete 04-algorithms_on_strings 04-suffix_array --- .../04-suffix_array/01-kmp/kmp.cpp | 24 +++++++++++++++------- 1 file changed, 17 insertions(+), 7 deletions(-) (limited to '04-algorithms_on_strings/04-suffix_array/01-kmp') 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 find_pattern(const string& pattern, const string& text) { - vector result; - // Implement this function yourself - return result; +vector find_pattern(const string& pattern, const string& text) +{ + vector result; + string s = pattern + "$" + text; + vector 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() { -- cgit v1.2.3