' Pattern matching algorithms: naive search, wildcard, palindrome
#COMPILE EXE
#DIM ALL

FUNCTION NaiveSearch(BYVAL text AS STRING, BYVAL pattern AS STRING) AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL n  AS LONG
    LOCAL m  AS LONG
    n = LEN(text)
    m = LEN(pattern)
    IF m = 0 OR m > n THEN FUNCTION = -1: EXIT FUNCTION
    FOR i = 1 TO n - m + 1
        FOR j = 0 TO m - 1
            IF MID$(text, i + j, 1) <> MID$(pattern, j + 1, 1) THEN EXIT FOR
        NEXT j
        IF j = m THEN FUNCTION = i: EXIT FUNCTION
    NEXT i
    FUNCTION = -1
END FUNCTION

FUNCTION WildcardMatch(BYVAL text AS STRING, BYVAL pattern AS STRING) AS LONG
    LOCAL t  AS LONG
    LOCAL p  AS LONG
    LOCAL starPos  AS LONG
    LOCAL matchPos  AS LONG
    t = 1
    p = 1
    starPos = -1
    matchPos = 1
    DO WHILE t <= LEN(text)
        IF p <= LEN(pattern) THEN
            IF MID$(pattern, p, 1) = "?" OR MID$(pattern, p, 1) = MID$(text, t, 1) THEN
                t = t + 1
                p = p + 1
            ELSEIF MID$(pattern, p, 1) = "*" THEN
                starPos = p
                matchPos = t
                p = p + 1
            ELSEIF starPos >= 0 THEN
                p = starPos + 1
                matchPos = matchPos + 1
                t = matchPos
            ELSE
                FUNCTION = 0: EXIT FUNCTION
            END IF
        ELSE
            EXIT LOOP
        END IF
    LOOP
    DO WHILE p <= LEN(pattern) AND MID$(pattern, p, 1) = "*"
        p = p + 1
    LOOP
    IF p > LEN(pattern) THEN FUNCTION = 1 ELSE FUNCTION = 0
END FUNCTION

FUNCTION IsPalindrome(BYVAL s AS STRING) AS LONG
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL n  AS LONG
    n = LEN(s)
    i = 1
    j = n
    DO WHILE i < j
        IF UCASE$(MID$(s, i, 1)) <> UCASE$(MID$(s, j, 1)) THEN FUNCTION = 0: EXIT FUNCTION
        i = i + 1
        j = j - 1
    LOOP
    FUNCTION = 1
END FUNCTION

SUB PrintAllMatches(BYVAL text AS STRING, BYVAL pattern AS STRING)
    PRINT "Text: " + CHR$(34) + text + CHR$(34)
    PRINT "Pattern: " + CHR$(34) + pattern + CHR$(34)
    PRINT "Naive search at: "
    PRINT NaiveSearch(text, pattern)
    IF WildcardMatch(text, pattern) THEN
        PRINT "Wildcard match: Yes"
    ELSE
        PRINT "Wildcard match: No"
    END IF
    PRINT
END SUB

FUNCTION PBMAIN() AS LONG
    LOCAL text AS STRING
    PRINT "=== Pattern Matching ==="
    PRINT
    CALL PrintAllMatches("Hello World, this is PBXB64", "World")
    CALL PrintAllMatches("abcdef", "xyz")
    text = "A man a plan a canal panama"
    PRINT "Is " + CHR$(34) + text + CHR$(34) + " a palindrome? "
    IF IsPalindrome(text) THEN PRINT "Yes" ELSE PRINT "No"
    PRINT
    PRINT "Wildcard demos:"
    IF WildcardMatch("hello", "h*") THEN PRINT "hello matches h*" ELSE PRINT "hello no"
    IF WildcardMatch("hello", "h??lo") THEN PRINT "hello matches h??lo" ELSE PRINT "hello no"
    IF WildcardMatch("world", "w*r*") THEN PRINT "world matches w*r*" ELSE PRINT "world no"
    IF WildcardMatch("test", "t?st") THEN PRINT "test matches t?st" ELSE PRINT "test no"
    IF WildcardMatch("foo", "bar") THEN PRINT "foo matches bar" ELSE PRINT "foo no"
    PRINT
    PRINT "Pattern matching tests complete."
    FUNCTION = 0
END FUNCTION
