Longest Common Subsequence

The longest common subsequence (LCS) is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

• C#
• VB.Net
• C
• C++

									Private Shared Function MAX(a As Integer, b As Integer) As Integer
	Return If(a > b, a, b)
End Function

Public Shared Function LongestCommonSubsequence(s1 As String, s2 As String, ByRef output As String) As Integer
	Dim i As Integer, j As Integer, k As Integer, t As Integer
	Dim s1Len As Integer = s1.Length
	Dim s2Len As Integer = s2.Length
	Dim z As Integer() = New Integer((s1Len + 1) * (s2Len + 1) - 1) {}
	Dim c As Integer(,) = New Integer((s1Len + 1) - 1, (s2Len + 1) - 1) {}

	For i = 0 To s1Len
		c(i, 0) = z(i * (s2Len + 1))
	Next

	For i = 1 To s1Len
		For j = 1 To s2Len
			If s1(i - 1) = s2(j - 1) Then
				c(i, j) = c(i - 1, j - 1) + 1
			Else
				c(i, j) = MAX(c(i - 1, j), c(i, j - 1))
			End If
		Next
	Next

	t = c(s1Len, s2Len)
	Dim outputSB As Char() = New Char(t - 1) {}

	i = s1Len
	j = s2Len
	k = t - 1
	While k >= 0
		If s1(i - 1) = s2(j - 1) Then
			outputSB(k) = s1(i - 1)
			i -= 1
			j -= 1
			k -= 1
		ElseIf c(i, j - 1) > c(i - 1, j) Then
			j -= 1
		Else
			i -= 1
		End If
	End While

	output = New String(outputSB)

	Return t
End Function
								

Example

									Dim s1 As String = "human"
Dim s2 As String = "chimpanzee"
Dim output As String = ""
Dim outputLen As Integer = LongestCommonSubsequence(s1, s2, output)
								

Output

									output: hman
outputLen: 4