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$)