Knuth–Morris–Pratt Algorithm

Knuth–Morris–Pratt (a.k.a KMP Algorithm) is a string search algorithm. it searches for occurrences of a sub-string within a main-string by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

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

									Public Shared Function SearchString(str As String, pat As String) As Integer()
	Dim retVal As New List(Of Integer)()
	Dim M As Integer = pat.Length
	Dim N As Integer = str.Length
	Dim i As Integer = 0
	Dim j As Integer = 0
	Dim lps As Integer() = New Integer(M - 1) {}

	ComputeLPSArray(pat, M, lps)

	While i < N
		If pat(j) = str(i) Then
			j += 1
			i += 1
		End If

		If j = M Then
			retVal.Add(i - j)
			j = lps(j - 1)

		ElseIf i < N AndAlso pat(j) <> str(i) Then
			If j <> 0 Then
				j = lps(j - 1)
			Else
				i = i + 1
			End If
		End If
	End While

	Return retVal.ToArray()
End Function

Private Shared Sub ComputeLPSArray(pat As String, m As Integer, lps As Integer())
	Dim len As Integer = 0
	Dim i As Integer = 1

	lps(0) = 0

	While i < m
		If pat(i) = pat(len) Then
			len += 1
			lps(i) = len
			i += 1
		Else
			If len <> 0 Then
				len = lps(len - 1)
			Else
				lps(i) = 0
				i += 1
			End If
		End If
	End While
End Sub
								

Example

									Dim data = "the quick brown fox jumps over the lazy dog"
Dim value = SearchString(data, "the")
								

Output

									0
31