102 lines
3 KiB
Text
102 lines
3 KiB
Text
-- demo\rosetta\BoyerMoore.exw
|
|
-- based on https://www-igm.univ-mlv.fr/~lecroq/string/node14.html
|
|
with javascript_semantics
|
|
function preBmBc(string pat)
|
|
integer m = length(pat)
|
|
sequence bmBc = repeat(m,255)
|
|
for i=1 to m-1 do
|
|
bmBc[pat[i]] = m - i
|
|
end for
|
|
return bmBc
|
|
end function
|
|
|
|
function suffixes(string pat)
|
|
integer m = length(pat), g = m, f
|
|
sequence suff = repeat(0,m)
|
|
suff[m] = m;
|
|
for i=m-1 to 1 by -1 do
|
|
if i > g and suff[i + m - f] < i - g then
|
|
suff[i] = suff[i + m - f]
|
|
else
|
|
if i < g then g = i end if
|
|
f = i
|
|
while g >= 1 and pat[g] == pat[g + m - f] do
|
|
g -= 1;
|
|
end while
|
|
suff[i] = f - g
|
|
end if
|
|
end for
|
|
return suff
|
|
end function
|
|
|
|
function preBmGs(string pat)
|
|
integer m = length(pat), j = 1
|
|
sequence suff = suffixes(pat),
|
|
bmGs = repeat(m,m)
|
|
for i=m to 1 by -1 do
|
|
if (suff[i] == i) then
|
|
while j < m - i do
|
|
if (bmGs[j] == m) then
|
|
bmGs[j] = m - i;
|
|
end if
|
|
j += 1
|
|
end while
|
|
end if
|
|
end for
|
|
for i=1 to m-1 do
|
|
bmGs[m - suff[i]] = m - i;
|
|
end for
|
|
return bmGs
|
|
end function
|
|
|
|
procedure BM(string pat, s, bool case_insensitive = false)
|
|
string pins = sprintf("`%s` in `%s`",{pat,shorten(s,"characters",10)})
|
|
if case_insensitive then
|
|
pat = lower(pat)
|
|
s = lower(s)
|
|
end if
|
|
/* Preprocessing */
|
|
sequence bmGs = preBmGs(pat),
|
|
bmBc = preBmBc(pat)
|
|
/* Searching */
|
|
sequence res = {}
|
|
integer i, j = 0,
|
|
n = length(s),
|
|
m = length(pat),
|
|
cc = 0
|
|
while j <= n - m do
|
|
for i=m to 1 by -1 do
|
|
cc += 1
|
|
if pat[i]!=s[i+j] then exit end if
|
|
end for
|
|
if i<1 then
|
|
res &= j+1
|
|
j += bmGs[1];
|
|
else
|
|
j += max(bmGs[i], bmBc[s[i + j]] - m + i);
|
|
end if
|
|
end while
|
|
string ccs = sprintf("(%d character comparisons)",cc)
|
|
if length(res) then
|
|
string many = ordinant(length(res))
|
|
printf(1,"Found %s %s at %v %s\n",{pins,many,res,ccs})
|
|
else
|
|
printf(1,"No %s %s\n",{pins,ccs})
|
|
end if
|
|
end procedure
|
|
|
|
BM("GCAGAGAG","GCATCGCAGAGAGTATACAGTACG")
|
|
BM("TCTA","GCTAGCTCTACGAGTCTA")
|
|
BM("TAATAAA","GGCTATAATGCGTA")
|
|
BM("word","there would have been a time for such a word")
|
|
BM("needle","needle need noodle needle")
|
|
constant book = "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley"&
|
|
"DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand"&
|
|
"assemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented"
|
|
BM("put",book)
|
|
BM("and",book)
|
|
constant farm = "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with "&
|
|
"bales of all that alfalfa exchanged for milk."
|
|
BM("alfalfa",farm)
|
|
--BM("aLfAlfa",farm) -- none
|
|
--BM("aLfAlfa",farm,true) -- as -2
|