Longest Common Substring

Longest common substring is an algorithm that finds the longest string that is a substring of two or more strings.

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

									Public Shared Function LongestCommonSubstring(str1 As String, str2 As String, ByRef subStr As String) As Integer
	subStr = String.Empty

	If String.IsNullOrEmpty(str1) OrElse String.IsNullOrEmpty(str2) Then
		Return 0
	End If

	Dim num As Integer(,) = New Integer(str1.Length - 1, str2.Length - 1) {}
	Dim maxlen As Integer = 0
	Dim lastSubsBegin As Integer = 0
	Dim subStrBuilder As New StringBuilder()

	For i As Integer = 0 To str1.Length - 1
		For j As Integer = 0 To str2.Length - 1
			If str1(i) <> str2(j) Then
				num(i, j) = 0
			Else
				If (i = 0) OrElse (j = 0) Then
					num(i, j) = 1
				Else
					num(i, j) = 1 + num(i - 1, j - 1)
				End If

				If num(i, j) > maxlen Then
					maxlen = num(i, j)

					Dim thisSubsBegin As Integer = i - num(i, j) + 1

					If lastSubsBegin = thisSubsBegin Then
						subStrBuilder.Append(str1(i))
					Else
						lastSubsBegin = thisSubsBegin
						subStrBuilder.Length = 0
						subStrBuilder.Append(str1.Substring(lastSubsBegin, (i + 1) - lastSubsBegin))
					End If
				End If
			End If
		Next
	Next

	subStr = subStrBuilder.ToString()

	Return maxlen
End Function
								

Example

									Dim str1 = "the quick brown fox jumps over the lazy dog"
Dim str2 = "ghdsgf fjsdfg ghdsfbrown fox jumpshfsdjfg 457877fsdfhb$%"
Dim value = String.Empty
LongestCommonSubstring(str1, str2, value)
								

Output

									brown fox jumps