Boyer-Moore string search: Difference between revisions
→{{header|J}}: full boyer-moore algorithm
m (→{{header|J}}) |
(→{{header|J}}: full boyer-moore algorithm) |
||
Line 70:
=={{header|J}}==
{{trans|Emacs Lisp}}
<lang J>
startPos=. 0
rightMap=. (i.#x) (3 u: x)} 256#_1
Line 92:
Example use:
<lang J> 'alfalfa'
55</lang>
Caution:
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}}==
|