1 ! Copyright (C) 2010 Dmitry Shubin.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: boyer-moore.private help.markup help.syntax kernel sequences ;
8 { "pattern" sequence } { "boyer-moore" boyer-moore }
11 "Given a pattern performs pattern preprocessing and returns "
12 "results as an (opaque) object that is reusable across "
13 "searches in different sequences via " { $link search-from } "."
16 "USING: boyer-moore prettyprint ;"
17 "\"abc\" <boyer-moore> ."
20 { bad-char-table H{ { 97 0 } { 98 -1 } { 99 -2 } } }
21 { good-suffix-table { 3 3 1 } }
29 { "from" "a non-negative integer" }
31 { "i/f" "the index of first match or " { $link f } }
33 { $contract "Performs an attempt to find the first "
34 "occurrence of pattern in " { $snippet "seq" }
35 " starting from " { $snippet "from" } " using "
36 "Boyer-Moore search algorithm. Output is the index "
37 "if the attempt was succeessful, or " { $link f }
41 "USING: boyer-moore prettyprint ;"
42 "{ 1 2 7 10 20 2 7 10 } 3 { 2 7 10 } search-from ."
51 { "i/f" "the index of first match or " { $link f } }
53 { $description "A simpler variant of " { $link search-from }
54 " that starts searching from the beginning of the sequence."
57 "USING: boyer-moore prettyprint ;"
58 "\"Source string\" \"ce st\" search ."
63 ARTICLE: "boyer-moore" "The Boyer-Moore algorithm"
64 { $heading "Summary" }
65 "The " { $vocab-link "boyer-moore" } " vocabulary "
66 "implements a Boyer-Moore string search algorithm with the "
67 "so-called 'strong good suffix shift rule'. Since the algorithm is "
68 "alphabet-independent, it is applicable to searching in any "
69 "collection that implements the " { $links "sequence-protocol" } "."
71 { $heading "Complexity" }
72 "Let " { $snippet "n" } " and " { $snippet "m" } " be the lengths "
73 "of the sequences being searched " { $emphasis "in" } " and "
74 { $emphasis "for" } " respectively. Then searching runs in "
75 { $snippet "O(n)" } " time worst-case, using additional "
76 { $snippet "O(m)" } " space. The preprocessing phase runs in "
77 { $snippet "O(m)" } " time."