Boyer-Moore string search: Difference between revisions
Added Yabasic
m (→{{header|Wren}}: Changed to Wren S/H) |
(Added Yabasic) |
||
Line 2,122:
Found 'alfalfa' in 'text6' at indices [33, 87]
</pre>
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="vb">case_insensitive = false
sub preBmBc(pat$)
local m, i
m = len(pat$)
redim bmBc(m)
for i = 1 to m-1
bmBc(val(mid$(pat$, i, 1))) = m - i
next
end sub
sub suffixes(pat$)
local m, g, i, f
m = len(pat$)
g = m
redim suff(m)
suff(m) = m
for i = m-1 to 1 step -1
if i > g and suff(i + m - f) < i - g then
suff(i) = suff(i + m - f)
else
if i < g g = i
f = i
while g >= 1 and mid$(pat$, g, 1) = mid$(pat$, g + m - f, 1)
g = q - 1
wend
suff(i) = f - g
fi
next
end sub
sub preBmGs(pat$)
local m, j, i
m = len(pat$)
j = 1
redim suff(m)
redim bmGs(m)
for i = m to 1 step -1
if suff(i) = i then
while j < m - i
if bmGs(j) = m bmGs(j) = m - i
j = j + 1
wend
fi
next
for i = 1 to m-1
bmGs(m - suff(i)) = m - i
next
end sub
sub BM(pat$, s$, case_insensitive)
local pins
pins$ = "'" + pat$ + "' in " + "'" + s$ + "'"
if case_insensitive then
pat$ = lower$(pat$)
s$ = lower$(s$)
fi
//* Preprocessing *//
preBmGs(pat$)
preBmBc(pat$)
//* Searching *//
j = 0
n = len(s$)
m = len(pat$)
i = m
while j <= n - m
i = i - 1
if mid$(pat$,i,1) <> mid$(s$,i+j,1) break
if i < 1 then j = j + bmGs(0) else j = j + max(bmGs(i), bmBc(len(mid$(s$,i+j,1)) - m + i)) : fi
wend
many = instr(s$, pat$)
tmp$ = ""
if not many > 0 then
print "No ", pins$
else
while many > 0 //if not found loop will be skipped
tmp$ = tmp$ + str$(many) + ","
many = instr(s$, pat$, many + 1)
wend
print "Found ", pins$, " at indices [", tmp$, chr$(8), "]"
fi
end sub
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")
book$ = "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented"
BM("put",book$)
BM("and",book$)
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$)</syntaxhighlight>
{{out}}
<pre>Same as QBasic entry.</pre>
| |||