Boyer-Moore string search: Difference between revisions

→‎{{header|J}}: full boyer-moore algorithm
(→‎{{header|J}}: full boyer-moore algorithm)
Line 70:
=={{header|J}}==
{{trans|Emacs Lisp}}
<lang J>bmsearchbmsearch0=: {{
startPos=. 0
rightMap=. (i.#x) (3 u: x)} 256#_1
Line 92:
 
Example use:
<lang J> 'alfalfa' bmsearchbmsearch0 'On behalf of an alfredo calfskin malfunction we donate alfalfa.'
55</lang>
 
Caution: this<tt>bmsearch0</tt> is an incomplete implementation of the algorithm. See talk page.
 
Here's a complete implementation of the algorithm:
 
<lang J>Z=: {{ y {{ 1 i.~y~:(#y){.m }}\.y }}
 
bmsearch1=: {{
mx=. <:nx=. #x
my=. <:ny=. #y
startPos=. 0
R=. |:>./\_1,(i.@# ([`]`((256#_1)"0))}&> 3&u:) x
L=. (-~ nx * *) Z&|. x
F=. >./\.(*]=#-i.@#) Z x
k=. mx
k0=. _1
while. k < ny do.
i=. mx
h=. k
while. (0<:i) * (k0<h) * (i{x) = h{y do.
i=. i-1
h=. h-1
end.
if. (_1=i)+.k0=h do.
1+k-nx return.
else.
if. mx=i do.
suffix_shift=. 1
elseif. _1=L{~i1=. i+1 do.
suffix_shift=. nx-F{~i1
else.
suffix_shift=. mx-L{~i1
end.
shift=. suffix_shift >. i-R{~<(3 u: h{y),i
if. shift > i do. k0=. k end.
k=. k + shift
end.
end.
EMPTY
}}</lang>
 
<lang J> 'alfalfa' bmsearch1 'On behalf of an alfredo calfskin malfunction we donate alfalfa.'
55</lang>
 
=={{header|Julia}}==
6,962

edits