Question

How to find the length of the longest common subsequence (LCS) in two strings with VB.NET

Answer 1

Public Class Program 
    Public Shared Function mymax(a As String, b As String) As Integer
        return If (a > b, a, b)
    End Function
    
    Public Shared Function lcs(s1 As String, s2 As String, lens1 As String, lens2 As String) As Integer
        If lens1 = 0 Or lens2 = 0 Then
            return 0
        End If
        If s1(lens1 - 1) = s2(lens2 - 1) Then
            return 1 + lcs(s1, s2, lens1 - 1, lens2 - 1)
        Else
            return mymax(lcs(s1, s2, lens1, lens2 - 1), lcs(s1, s2, lens1 - 1, lens2))
        End If
    End Function 
    
    Public Shared Sub Main()
        Dim s1 As String = "accyrb"
        Dim s2 As String = "cyxyazb"
  
        Console.WriteLine("Length of LCS is {0}", lcs(s1, s2, s1.Length, s2.Length)) 
    End Sub
End Class



' run:

' Length of LCS is 3

 

70+ SQL courses for beginners and professionals

Answer 2

Imports System

' This program computes BOTH:
'   1. The length of the Longest Common Subsequence (LCS)
'   2. The actual LCS subsequence
'
' It uses an efficient dynamic‑programming algorithm:
'       Time:  O(n * m)
'       Space: O(n * m)
'
' dp(i)(j) stores the LCS length between:
'       s1(0..i-1) and s2(0..j-1)
'
' Recurrence:
'   If characters match:
'       dp(i)(j) = dp(i-1)(j-1) + 1
'   Else:
'       dp(i)(j) = Math.Max(dp(i-1)(j), dp(i)(j-1))
'
' After filling the DP table, we reconstruct the LCS by
' walking backwards from dp(n)(m).

Module LCSProgram

    ' Function that returns both LCS length and the subsequence
    Function LCS(s1 As String, s2 As String) As Tuple(Of Integer, String)
        Dim n As Integer = s1.Length
        Dim m As Integer = s2.Length

        ' Create DP table initialized with zeros
        Dim dp(n, m) As Integer

        ' Fill DP table
        For i As Integer = 1 To n
            For j As Integer = 1 To m
                If s1(i - 1) = s2(j - 1) Then
                    dp(i, j) = dp(i - 1, j - 1) + 1
                Else
                    dp(i, j) = Math.Max(dp(i - 1, j), dp(i, j - 1))
                End If
            Next
        Next

        ' Reconstruct the LCS sequence
        Dim length As Integer = dp(n, m)
        Dim chars As Char() = New Char(length - 1) {}

        Dim x As Integer = n
        Dim y As Integer = m
        Dim index As Integer = length - 1

        While x > 0 AndAlso y > 0
            If s1(x - 1) = s2(y - 1) Then
                chars(index) = s1(x - 1)
                index -= 1
                x -= 1
                y -= 1
            ElseIf dp(x - 1, y) > dp(x, y - 1) Then
                x -= 1
            Else
                y -= 1
            End If
        End While

        Dim lcsString As String = New String(chars)
        Return Tuple.Create(length, lcsString)
    End Function

    Sub Main()
        Dim s1 As String = "AGGTAB"
        Dim s2 As String = "GXTXAYB"

        Dim result = LCS(s1, s2)

        Console.WriteLine("String 1: " & s1)
        Console.WriteLine("String 2: " & s2)
        Console.WriteLine("Length of LCS: " & result.Item1)
        Console.WriteLine("LCS sequence: " & result.Item2)
    End Sub

End Module



' run:
'
' String 1: AGGTAB
' String 2: GXTXAYB
' Length of LCS: 4
' LCS sequence: GTAB
'

 

70+ SQL courses for beginners and professionals