form1.vb

an lcs algorithm for finding common string

Public Class Form1

    Public Sub New()

        ' This call is required by the Windows Form Designer.
        InitializeComponent()

        ' Add any initialization after the InitializeComponent() call.
        We.See.Diff.IndexTestCode.TestIndex()
        We.See.Diff.DiffTestCode.TestDiff()

    End Sub

    Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        Dim t As String = Me.ComboBox1.Text
        Me.ComboBox1.Text = Me.ComboBox2.Text
        Me.ComboBox2.Text = t
    End Sub

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

        Dim a As String = ""
        Dim i As Integer = Subsequence(Me.ComboBox1.Text, Me.ComboBox2.Text, a)

        Me.TextBox1.Text = i & vbCrLf & vbCrLf & a

    End Sub

    Private Function PrintArray(ByVal num(,) As Long, ByVal s1 As String, ByVal s2 As String) As String
        Dim sb As New System.Text.StringBuilder
        sb.Append("  ")
        For j As Integer = 0 To UBound(num, 2)
            If j < s2.Length Then sb.Append(s2(j))
            sb.Append(" ")
        Next
        sb.Append(vbCrLf)
        For i As Integer = 0 To UBound(num, 1) - 1
            If i < s1.Length Then sb.Append(s1(i)) Else sb.Append(" ")
            sb.Append(" ")
            For j As Integer = 0 To UBound(num, 2) - 1
                sb.Append(num(i, j))
                sb.Append(" ")
            Next
            sb.Append(vbCrLf)
        Next
        Return sb.ToString
    End Function

    Private Function BackTrack(ByVal num(,) As Long, ByVal s1 As String, ByVal s2 As String, ByVal i As Integer, ByVal j As Integer)
        If i = 0 Or j = 0 Then Return ""

        If s1(i - 1) = s2(j - 1) Then
            Return BackTrack(num, s1, s2, i - 1, j - 1) & s1(i - 1)
        Else
            If num(i, j - 1) > num(i - 1, j) Then
                Return BackTrack(num, s1, s2, i, j - 1)
            Else
                Return BackTrack(num, s1, s2, i - 1, j)
            End If
        End If
    End Function

    Private Function printDiff(ByRef num(,) As Long, ByRef num2(,) As Long, ByVal s1 As String, ByVal s2 As String, ByVal i As Integer, ByVal j As Integer)

        If i > 0 AndAlso j > 0 AndAlso s1(i - 1) = s2(j - 1) Then
            If i > 0 AndAlso j > 0 Then num2(i - 1, j - 1) = 0
            Return printDiff(num, num2, s1, s2, i - 1, j - 1) & "  " + s1(i - 1) & vbCrLf
        Else
            If j > 0 AndAlso (i = 0 OrElse num(i, j - 1) >= (num(i - 1, j))) Then
                If i > 0 AndAlso j > 0 Then num2(i - 1, j - 1) = 9
                Return printDiff(num, num2, s1, s2, i, j - 1) & "+ " & s2(j - 1) & vbCrLf
            ElseIf i > 0 AndAlso (j = 0 OrElse num(i, j - 1) < num(i - 1, j)) Then
                If i > 0 AndAlso j > 0 Then num2(i - 1, j - 1) = 0
                Return printDiff(num, num2, s1, s2, i - 1, j) & "- " & s1(i - 1) & vbCrLf
            Else
                If i > 0 AndAlso j > 0 Then num2(i - 1, j - 1) = 7
                printDiff = ""
            End If
        End If

        'If i > 0 AndAlso j > 0 AndAlso s1(i - 1) = s2(j - 1) Then
        '    Return printDiff(num, num2, s1, s2, i - 1, j - 1) & "  " + s1(i - 1) & vbCrLf
        'Else
        '    If j > 0 AndAlso (i = 0 OrElse num(i, j - 1) >= (num(i - 1, j))) Then
        '        Return printDiff(num, num2, s1, s2, i, j - 1) & "+ " & s2(j - 1) & vbCrLf
        '    ElseIf i > 0 AndAlso (j = 0 OrElse num(i, j - 1) < num(i - 1, j)) Then
        '        Return printDiff(num, num2, s1, s2, i - 1, j) & "- " & s1(i - 1) & vbCrLf
        '    Else
        '        printDiff = ""
        '    End If
        'End If

    End Function

    Public Function Subsequence(ByVal s1 As String, ByVal s2 As String, ByRef arr As String) As Integer

        'Bulletproofing - 1 or both inputs contains nothing
        'If s1.Length.Equals(0) Or s2.Length.Equals(0) Then
        '    Return "0"
        'End If

        '*** Actual Algorithm From Here ***
        Dim num(s1.Length, s2.Length) As Long       '2D Array
        Dim letter1 As Char = Nothing
        Dim letter2 As Char = Nothing
        For i As Integer = 0 To s1.Length - 1

            For j As Integer = 0 To s2.Length - 1

                letter1 = s1.Chars(i)
                letter2 = s2.Chars(j)

                If letter1.Equals(letter2) Then
                    If i.Equals(0) Or j.Equals(0) Then  'The first elements respectively
                        num(i, j) = 1
                    Else
                        num(i, j) = 1 + num(i - 1, j - 1)
                    End If
                Else
                    If i.Equals(0) And j.Equals(0) Then
                        num(i, j) = 0
                    ElseIf i.Equals(0) And Not j.Equals(0) Then    'First ith element
                        num(i, j) = Math.Max(0, num(i, j - 1))
                    ElseIf j.Equals(0) And Not i.Equals(0) Then   'First jth element
                        num(i, j) = Math.Max(num(i - 1, j), 0)
                    ElseIf i <> 0 And j <> 0 Then
                        num(i, j) = Math.Max(num(i - 1, j), num(i, j - 1))
                    End If
                End If
            Next j
        Next i

        'For i As Integer = 0 To s1.Length - 1
        '    For j As Integer = 0 To s2.Length - 1
        '        num(i, j) = num(i, j) * 10
        '    Next
        'Next

        arr = PrintArray(num, s1, s2)

        Dim num2 As Long(,) = num.Clone()
        'For i As Integer = 0 To s1.Length - 1
        '    For j As Integer = 0 To s2.Length - 1
        '        num2(i, j) = 0
        '    Next
        'Next

        arr &= vbCrLf & BackTrack(num, s1, s2, s1.Length, s2.Length) & vbCrLf
        arr &= vbCrLf & printDiff(num, num2, s1, s2, s1.Length, s2.Length)

        arr &= vbCrLf & PrintArray(num2, s1, s2)

        For i As Integer = 0 To s1.Length - 1
            For j As Integer = 0 To s2.Length - 1
                num(i, j) = 0
            Next
        Next

        For i As Integer = 0 To s1.Length - 1

            For j As Integer = 0 To s2.Length - 1

                letter1 = s1.Chars(i)
                letter2 = s2.Chars(j)

                If letter1.Equals(letter2) Then
                    If i.Equals(0) Or j.Equals(0) Then  'The first elements respectively
                        num(i, j) = 1
                    Else
                        num(i, j) = 1 '+ num(i - 1, j - 1)
                    End If
                Else
                    'If i.Equals(0) And j.Equals(0) Then
                    '    num(i, j) = 0
                    'ElseIf i.Equals(0) And Not j.Equals(0) Then    'First ith element
                    '    num(i, j) = Math.Max(0, num(i, j - 1))
                    'ElseIf j.Equals(0) And Not i.Equals(0) Then   'First jth element
                    '    num(i, j) = Math.Max(num(i - 1, j), 0)
                    'ElseIf i <> 0 And j <> 0 Then
                    '    num(i, j) = Math.Max(num(i - 1, j), num(i, j - 1))
                    'End If
                End If
            Next j
        Next i

        ' arr &= vbCrLf & PrintArray(num, s1, s2)

        For i As Integer = 0 To s1.Length - 1
            For j As Integer = 0 To s2.Length - 1
                num(i, j) = 0
            Next
        Next

        For i As Integer = 0 To s1.Length - 1

            For j As Integer = 0 To s2.Length - 1

                letter1 = s1.Chars(i)
                letter2 = s2.Chars(j)

                If letter1.Equals(letter2) Then
                    If i.Equals(0) Or j.Equals(0) Then  'The first elements respectively
                        num(i, j) = 1
                    Else
                        num(i, j) = 1 + num(i - 1, j - 1)
                    End If
                Else
                    'If i.Equals(0) And j.Equals(0) Then
                    '    num(i, j) = 0
                    'ElseIf i.Equals(0) And Not j.Equals(0) Then    'First ith element
                    '    num(i, j) = Math.Max(0, num(i, j - 1))
                    'ElseIf j.Equals(0) And Not i.Equals(0) Then   'First jth element
                    '    num(i, j) = Math.Max(num(i - 1, j), 0)
                    'ElseIf i <> 0 And j <> 0 Then
                    '    num(i, j) = Math.Max(num(i - 1, j), num(i, j - 1))
                    'End If
                End If
            Next j
        Next i

        'arr &= vbCrLf & PrintArray(num, s1, s2)

        Dim s1a As New List(Of String)
        Dim s2a As New List(Of String)
        For i As Integer = 0 To s1.Length - 1
            s1a.Add(s1.Chars(i))
        Next

        For j As Integer = 0 To s2.Length - 1
            s2a.Add(s2.Chars(j))
        Next

        arr = "" ' LCS.LCSFinder.LCS(s1a.ToArray, s2a.ToArray)

        Dim DiffScript As We.See.Diff.DiffScript(Of String)
        DiffScript = We.See.Diff.DiffEngine(Of String).MakeDiffScript(s1a.ToArray, s2a.ToArray)

        arr &= vbCrLf & DiffScript.print
        DiffScript.Interpret()
        arr &= vbCrLf & DiffScript.print

        arr &= vbCrLf & String.Join("", s1a.ToArray)
        DiffScript.ApplyTo(s1a)
        arr &= vbCrLf & String.Join("", s1a.ToArray)
        arr &= vbCrLf & String.Join("", s2a.ToArray)

        Return 1 'num(s1.Length - 1, s2.Length - 1)

    End Function

    Public Function LongestCommonSubstring(ByVal s1 As String, ByVal s2 As String) As Integer
        Dim num(s1.Length - 1, s2.Length - 1) As Integer   '2D array
        Dim letter1 As Char = Nothing
        Dim letter2 As Char = Nothing
        Dim len As Integer = 0
        Dim ans As Integer = 0
        For i As Integer = 0 To s1.Length - 1
            For j As Integer = 0 To s2.Length - 1
                letter1 = s1.Chars(i)
                letter2 = s2.Chars(j)
                If Not letter1.Equals(letter2) Then
                    num(i, j) = 0
                Else
                    If i.Equals(0) Or j.Equals(0) Then
                        num(i, j) = 1
                    Else
                        num(i, j) = 1 + num(i - 1, j - 1)
                    End If
                    If num(i, j) > len Then
                        len = num(i, j)
                        ans = num(i, j)
                    End If
                End If
            Next j
        Next i
        Return ans
    End Function


End Class