103 lines
2.4 KiB
Text
103 lines
2.4 KiB
Text
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$)
|