From 533c9a2aa57cf3fd2967b2a72016322902584986 Mon Sep 17 00:00:00 2001 From: Mathias Gumz Date: Sat, 2 May 2015 14:04:50 +0200 Subject: Fix bug in detecting text in MenuSearch A bug sneaked into my implementation of Boyer-Moore-Horspool. This lead to not finding certain patterns. Given the text 'abcdde' and the pattern 'dd', the faulty implementation would not find 'dd': 1. 'ab' does not match, skip 2 (length of pattern) 2. 'cd' does not match, skip 2 (length of pattern) <- the bug. 3. 'de' does not match, end of string The bug in step 2 is to not use 'd' to detect how far to skip but to use 'c' (which is not in the skip-table) and thus 2 bytes are skipped). --- src/FbTk/MenuSearch.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/FbTk/MenuSearch.cc b/src/FbTk/MenuSearch.cc index d87bfaf..7efd232 100644 --- a/src/FbTk/MenuSearch.cc +++ b/src/FbTk/MenuSearch.cc @@ -75,7 +75,7 @@ size_t search_str_bmh(const std::string& text, const std::string& pattern) { return t+p; } } - t += skip[std::tolower(text[t+p])]; + t += skip[std::tolower(text[t+plast])]; } return std::string::npos; -- cgit v0.11.2