#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL text_str AS STRING
    LOCAL pattern AS STRING
    LOCAL bad_char(255) AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL text_len AS LONG
    LOCAL pat_len AS LONG
    LOCAL shift_val AS LONG
    LOCAL found_pos AS LONG
    LOCAL found_count AS LONG
    LOCAL temp_str AS STRING
    LOCAL c AS LONG

    PRINT "Boyer-Moore String Search"
    PRINT "========================="
    PRINT ""

    text_str = "the quick brown fox jumps over the lazy dog near the river bank"
    pattern = "the"

    text_len = LEN(text_str)
    pat_len = LEN(pattern)

    ' Build bad character shift table
    i = 0
    WHILE i < 256
        bad_char(i) = pat_len
        i = i + 1
    WEND

    i = 1
    WHILE i < pat_len
        bad_char(ASC(MID$(pattern, i, 1))) = pat_len - i
        i = i + 1
    WEND

    ' Search
    found_count = 0
    i = 1
    WHILE i <= text_len - pat_len + 1
        j = pat_len
        WHILE j >= 1 AND MID$(text_str, i + j - 1, 1) = MID$(pattern, j, 1)
            j = j - 1
        WEND

        IF j < 1 THEN
            found_pos = i
            found_count = found_count + 1
            temp_str = STR$(found_pos)
            PRINT "Found '" + pattern + "' at position " + temp_str + ": " + MID$(text_str, i, pat_len)
            i = i + pat_len
        ELSE
            c = ASC(MID$(text_str, i + pat_len - 1, 1))
            shift_val = bad_char(c)
            i = i + shift_val
        END IF
    WEND

    temp_str = STR$(found_count)
    PRINT ""
    PRINT "Total occurrences of 'the': " + temp_str

    ' Search for 'fox'
    pattern = "fox"
    pat_len = LEN(pattern)

    i = 0
    WHILE i < 256
        bad_char(i) = pat_len
        i = i + 1
    WEND

    i = 1
    WHILE i < pat_len
        bad_char(ASC(MID$(pattern, i, 1))) = pat_len - i
        i = i + 1
    WEND

    found_count = 0
    i = 1
    WHILE i <= text_len - pat_len + 1
        j = pat_len
        WHILE j >= 1 AND MID$(text_str, i + j - 1, 1) = MID$(pattern, j, 1)
            j = j - 1
        WEND
        IF j < 1 THEN
            found_count = found_count + 1
            temp_str = STR$(i)
            PRINT "Found '" + pattern + "' at position " + temp_str
            i = i + pat_len
        ELSE
            c = ASC(MID$(text_str, i + pat_len - 1, 1))
            shift_val = bad_char(c)
            i = i + shift_val
        END IF
    WEND

    ' Search for 'xyz' (no match)
    pattern = "xyz"
    pat_len = LEN(pattern)

    i = 0
    WHILE i < 256
        bad_char(i) = pat_len
        i = i + 1
    WEND

    i = 1
    WHILE i < pat_len
        bad_char(ASC(MID$(pattern, i, 1))) = pat_len - i
        i = i + 1
    WEND

    found_count = 0
    i = 1
    WHILE i <= text_len - pat_len + 1
        j = pat_len
        WHILE j >= 1 AND MID$(text_str, i + j - 1, 1) = MID$(pattern, j, 1)
            j = j - 1
        WEND
        IF j < 1 THEN
            found_count = found_count + 1
        ELSE
            c = ASC(MID$(text_str, i + pat_len - 1, 1))
            shift_val = bad_char(c)
            i = i + shift_val
        END IF
    WEND

    temp_str = STR$(found_count)
    PRINT "Occurrences of 'xyz': " + temp_str

    ' Bad character table demo
    PRINT ""
    PRINT "Bad character shift table for 'the':"
    i = 0
    WHILE i < 256
        IF bad_char(i) > 0 AND bad_char(i) < pat_len THEN
            temp_str = CHR$(i)
            IF i >= 32 AND i <= 126 THEN
                PRINT "  '" + temp_str + "' (ASCII " + STR$(i) + "): shift " + STR$(bad_char(i))
            END IF
        END IF
        i = i + 1
    WEND

    PRINT ""
    PRINT "Boyer-Moore search complete."

    FUNCTION = 0
END FUNCTION
