Question Greedy string tilting algorithm

[awo84]

Hello everyone,
I'm currently working on a greedy string tiling algorithm to find out matches between two strings, but there is something wrong with the string, they are not marked right so can you help me guys?

Here is the code am trying:

Sub GST2(ByVal str1 As Array, ByVal str2 As Array)
        Dim a, b, j, cnt, jj, max_a, max_b As Integer

        ' Do While maxmatch > 3
        cnt = 0
        maxmatch = 2



        For a = 0 To str1.Length - 1
            'new index to put a new tile in
            cnt += 1
            maxmatch = 2
            max_a = 0
            max_b = 0
            jj = 1
            For b = 0 To str2.Length - 1
                j = 0

                'same chars and not marked
                While str1(a + j) = str2(b + j) And str1(a + j) <> "" And str2(b + j) <> ""
                    If b + j <= str2.Length - 1 Or a + j <= str1.Length - 1 Then
                        j += 1
                    Else
                        j += 1
                        Exit While
                    End If

                End While

                'we got a larger match
                If j > maxmatch Then
                    match(a, b, j, cnt)
                    max_a = a
                    max_b = b
                    maxmatch = j
                    jj = j

                Else
                   
                    End If

            Next

            mark(max_a, max_b, jj, str1, str2)

        Next

        printArray()
        Dim i As Integer
        For i = 0 To str1.Length - 1
            TextBox6.Text = TextBox6.Text & vbCrLf & ar(i)
        Next
        For i = 0 To str2.Length - 1
            TextBox7.Text = TextBox7.Text & vbCrLf & ar2(i)
        Next
    End Sub

    

    Sub match(ByVal a As Integer, ByVal b As Integer, ByVal c As Integer, ByVal cnt As Integer)

        MyArray(cnt, 0) = a
        MyArray(cnt, 1) = b
        MyArray(cnt, 2) = c



    End Sub
    Sub mark(ByVal a As Integer, ByVal b As Integer, ByVal j As Integer, ByRef str1 As Array, ByRef str2 As Array)
        Dim i As Integer
        For i = a To i + j - 1
            str1(i) = ""
        Next
        For i = b To i + j - 1
            str2(i) = ""
        Next
    End Sub

    Sub printArray()
        Dim output As String = ""
        Dim i, j As Integer

        For i = 0 To MyArray.GetUpperBound(0)

            For j = 0 To MyArray.GetUpperBound(1)
                output += MyArray(i, j) & "   "
            Next
            output &= vbCrLf
        Next
        TextBox5.Text = output
    End Sub


    Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        GST2(ar, ar2)
    End Sub

    
End Class

 

[awo84]

Here's the algorithm





0 Greedy-String-Tiling(String A, String B) {

1 tiles = {};

2 do {

3 maxmatch = M;

4 matches = {};

5 Forall unmarked tokens Aa in A {

6 Forall unmarked tokens Bb in B {

7 j= 0;

8 while (Aa+j == Bb+j &&

9 unmarked(Aa+j) && unmarked(Bb+j))

10 j ++;

11 if (j == maxmatch)

12 matches = matches ⊕ match(a, b, j);

13 else if (j >maxmatch) {

14 matches = {match(a, b, j)};

15 maxmatch = j;

16 }

17 }

18 }

19 Forall match(a, b, maxmatch) ∈ matches {

20 For j = 0. . . (maxmatch− 1) {

21 mark(Aa+j);

22 mark(Bb+j );

23 }

24 tiles = tiles ∪ match(a, b, maxmatch);

25 } 26 } while (maxmatch > M);

27 return tiles;

28 }

 

[Tom]

Wow all of that hurts my head even trying to decipher it. Since your asking others for help, why not try making it easier for others to actually help you by:
giving your variable & even controls a more descriptive & meaningfull names, adding commenting to your coding,
limiting and pointing out exactly where in the code your having the problem etc...

Or are those helping you expected to try and figure out what str1, str2, a, b, j all are and what there doing...

               While str1(a + j) = str2(b + j) And str1(a + j) <> "" And str2(b + j) <> ""
                    If b + j <= str2.Length - 1 Or a + j <= str1.Length - 1 Then
                        j += 1
                    Else
                        j += 1
                        Exit While
                    End If

                End While

 

[Falke]

The Code, as given, is not working
declaration are missing for:
- MyArray
- maxmatch
- ar
- ar2