Boyer–Moore lazarus / 21-General ---------------------------------------------------------------------- Tirans · 2021-02-16 14:24 Hey, does anyone have a plain Boyer–Moore algorithm that they could share? ---------------------------------------------------------------------- howardpc · 2021-02-16 14:47 See https://forum.lazarus.freepascal.org/index.php/topic,18805.msg1064 03.html#msg106403 ---------------------------------------------------------------------- lucamar · 2021-02-16 15:47 See also: FindMatchesBoyerMooreCaseSensitive and FindMatchesBoyerMooreCaseInsensitive, in the StrUtils unit (RTL). ---------------------------------------------------------------------- avk · 2021-02-18 08:06 Quote from: lucamar on February 16, 2021, 04:47:20 pmSee also: FindMatchesBoyerMooreCaseSensitive and FindMatchesBoyerMooreCaseInsensitive, in the StrUtils unit (RTL). It seems to be buggy. At least for the pattern "abcab" and the text "abcabcabcabcabcabcab" it indicates the match positions [1, 7, 13], but it should be [1, 4, 7, 10, 13]. ---------------------------------------------------------------------- lucamar · 2021-02-18 09:24 Quote from: avk on February 18, 2021, 09:06:33 amIt seems to be buggy. At least for the pattern "abcab" and the text "abcabcabcabcabcabcab" it indicates the match positions [1, 7, 13], but it should be [1, 4, 7, 10, 13]. That's how the "normal" Boyer-Moore behaves in border cases like that: when it finds a match it advances the index to the first char after it, missing the "partial match" inside the one already found. For strings like that, another algorithm must be used. ---------------------------------------------------------------------- avk · 2021-02-18 09:56 You think so? In any case, the documentation states otherwise: QuoteFindMatchesBoyerMooreCaseSensitive finds occurrences of OldPattern (with length OldPatternSize) in S(with length SSize). The search is performed case-sensitively, and all (zero based) positions are reported in aMatches. If aMatchAll is True, all positions will be reported. If aMatchAll is False, only the first position is reported. ---------------------------------------------------------------------- avk · 2021-02-19 05:37 I reported a bug, let's see what happens. ---------------------------------------------------------------------- avk · 2021-02-21 04:08 In addition, the above implementation has another drawback - it does not allow reusing of pattern preprocessing. Therefore, regardless of whether my patch is accepted or not, I'll try to add some kind of exact string matching algorithm to LGenerics. ---------------------------------------------------------------------- avk · 2021-02-22 06:03 Done.