#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL str1 AS STRING
    LOCAL str2 AS STRING
    LOCAL len_a AS LONG
    LOCAL len_b AS LONG
    LOCAL d(400) AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL cost AS LONG
    LOCAL temp_val AS LONG
    LOCAL temp_str AS STRING

    PRINT "Levenshtein Edit Distance"
    PRINT "========================"
    PRINT ""

    ' Test 1: kitten -> sitting
    str1 = "kitten"
    str2 = "sitting"
    len_a = LEN(str1)
    len_b = LEN(str2)

    i = 0
    WHILE i <= len_a
        d(i * (len_b + 1) + 0) = i
        i = i + 1
    WEND

    j = 0
    WHILE j <= len_b
        d(0 * (len_b + 1) + j) = j
        j = j + 1
    WEND

    i = 1
    WHILE i <= len_a
        j = 1
        WHILE j <= len_b
            cost = 0
            IF MID$(str1, i, 1) <> MID$(str2, j, 1) THEN
                cost = 1
            END IF

            d(i * (len_b + 1) + j) = d((i - 1) * (len_b + 1) + j) + 1
            temp_val = d(i * (len_b + 1) + (j - 1)) + 1
            IF temp_val < d(i * (len_b + 1) + j) THEN
                d(i * (len_b + 1) + j) = temp_val
            END IF
            temp_val = d((i - 1) * (len_b + 1) + (j - 1)) + cost
            IF temp_val < d(i * (len_b + 1) + j) THEN
                d(i * (len_b + 1) + j) = temp_val
            END IF

            j = j + 1
        WEND
        i = i + 1
    WEND

    temp_str = STR$(d(len_a * (len_b + 1) + len_b))
    PRINT "'kitten' -> 'sitting' = " + temp_str + " edits"

    ' Test 2: Saturday -> Sunday
    str1 = "Saturday"
    str2 = "Sunday"
    len_a = LEN(str1)
    len_b = LEN(str2)

    i = 0
    WHILE i <= len_a
        d(i * (len_b + 1) + 0) = i
        i = i + 1
    WEND
    j = 0
    WHILE j <= len_b
        d(0 * (len_b + 1) + j) = j
        j = j + 1
    WEND

    i = 1
    WHILE i <= len_a
        j = 1
        WHILE j <= len_b
            cost = 0
            IF MID$(str1, i, 1) <> MID$(str2, j, 1) THEN
                cost = 1
            END IF
            d(i * (len_b + 1) + j) = d((i - 1) * (len_b + 1) + j) + 1
            temp_val = d(i * (len_b + 1) + (j - 1)) + 1
            IF temp_val < d(i * (len_b + 1) + j) THEN
                d(i * (len_b + 1) + j) = temp_val
            END IF
            temp_val = d((i - 1) * (len_b + 1) + (j - 1)) + cost
            IF temp_val < d(i * (len_b + 1) + j) THEN
                d(i * (len_b + 1) + j) = temp_val
            END IF
            j = j + 1
        WEND
        i = i + 1
    WEND

    temp_str = STR$(d(len_a * (len_b + 1) + len_b))
    PRINT "'Saturday' -> 'Sunday' = " + temp_str + " edits"

    ' Test 3: hello -> hello (identical)
    str1 = "hello"
    str2 = "hello"
    len_a = LEN(str1)
    len_b = LEN(str2)

    i = 0
    WHILE i <= len_a
        d(i * (len_b + 1) + 0) = i
        i = i + 1
    WEND
    j = 0
    WHILE j <= len_b
        d(0 * (len_b + 1) + j) = j
        j = j + 1
    WEND

    i = 1
    WHILE i <= len_a
        j = 1
        WHILE j <= len_b
            cost = 0
            IF MID$(str1, i, 1) <> MID$(str2, j, 1) THEN cost = 1
            d(i * (len_b + 1) + j) = d((i - 1) * (len_b + 1) + j) + 1
            temp_val = d(i * (len_b + 1) + (j - 1)) + 1
            IF temp_val < d(i * (len_b + 1) + j) THEN d(i * (len_b + 1) + j) = temp_val
            temp_val = d((i - 1) * (len_b + 1) + (j - 1)) + cost
            IF temp_val < d(i * (len_b + 1) + j) THEN d(i * (len_b + 1) + j) = temp_val
            j = j + 1
        WEND
        i = i + 1
    WEND

    temp_str = STR$(d(len_a * (len_b + 1) + len_b))
    PRINT "'hello' -> 'hello' = " + temp_str + " edits"

    ' Test 4: abc -> xyz (completely different)
    str1 = "abc"
    str2 = "xyz"
    len_a = 3
    len_b = 3

    i = 0
    WHILE i <= len_a
        d(i * (len_b + 1) + 0) = i
        i = i + 1
    WEND
    j = 0
    WHILE j <= len_b
        d(0 * (len_b + 1) + j) = j
        j = j + 1
    WEND

    i = 1
    WHILE i <= len_a
        j = 1
        WHILE j <= len_b
            cost = 0
            IF MID$(str1, i, 1) <> MID$(str2, j, 1) THEN cost = 1
            d(i * (len_b + 1) + j) = d((i - 1) * (len_b + 1) + j) + 1
            temp_val = d(i * (len_b + 1) + (j - 1)) + 1
            IF temp_val < d(i * (len_b + 1) + j) THEN d(i * (len_b + 1) + j) = temp_val
            temp_val = d((i - 1) * (len_b + 1) + (j - 1)) + cost
            IF temp_val < d(i * (len_b + 1) + j) THEN d(i * (len_b + 1) + j) = temp_val
            j = j + 1
        WEND
        i = i + 1
    WEND

    temp_str = STR$(d(3 * 4 + 3))
    PRINT "'abc' -> 'xyz' = " + temp_str + " edits"

    PRINT ""
    PRINT "Levenshtein distance complete."

    FUNCTION = 0
END FUNCTION
