Boyer-Moore string search: Difference between revisions

=={{header|J}}==

{{trans|Emacs Lisp}}

startPos=. 0

rightMap=. (i.#x) (3 u: x)} 256#_1

end.

''

 

Example use:

 

Caution: <tt>bmsearch0</tt> is an incomplete implementation of the algorithm. See talk page.

Here's a complete implementation of the algorithm:

 

 

bmsearch1=: {{

end.

EMPTY

 

 

Testing performance on a relatively long text (and pattern):

 

pat=. text{~9e6+i.1e5

pat bmsearch0 text

9000000

'pat bmsearch0 text' %&timex 'pat bmsearch1 text'

 

In other words: <tt>bmsearch0</tt> takes slightly over twice as long as <tt>bmsearch1</tt> for a somewhat randomly picked example search (though the results are the same).

"Algorithms on Strings, Trees, and Sequences", 1997, available online as a pdf in several publicly indexed

archives on the internet.

 

const ASCIIchars = String([Char(i) for i = 0:255]) # any standard or extended ASCII char

occurrences, num_alignments, num_character_comparisons = boyer_moore_with_counts(p7, p_bm7, t7)

@show occurrences, num_alignments, num_character_comparisons

<pre>

(p_bm.amap, p_bm.bad_char) = (Dict('A' => 1, 'G' => 3, 'T' => 4, 'C' => 2), [[0, 0, 0, 0], [0, 0, 0, 1], [0, 2, 0, 1], [3, 2, 0, 1]])

=={{header|Python}}==

Slightly modified from en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Python_implementation.

This version uses ASCII for case-sensitive matching. For Unicode you may want to match in UTF-8

bytes instead of creating a 0x10FFFF-sized table.

print("Found", PAT2, "at:", string_search(PAT2, TEXT1))

print("Found", PAT3, "at:", string_search(PAT3, TEXT2))

<pre>

Found put at: [26, 90]

=={{header|Raku}}==

{{trans|Phix}}

 

sub suffixes (@pat,\m) {

my \j = $_ < 6 ?? $_ !! $_-1 ; # for searching text5 twice

say "Found '@pats[$_]' in 'text{j}' at indices ", BM @texts[j].comb, @pats[$_].comb

Output is the same as the [[Knuth-Morris-Pratt_string_search#Raku]] entry.

 

 

The same examples have been used as in the Julia entry above.

/**

* Returns the index within this string of the first occurrence of the

var j = (i < 5) ? i : i-1

System.print("Found '%(pats[i])' in 'text%(j+1)' at indices %(indicesOf.call(texts[j], pats[i]))")

 

{{out}}