Finite-State Automaton

Finite-State Automaton is a string searching algorithm.

• 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, state As Integer = 0
	Dim TF As Integer(,) = New Integer(M, 255) {}

	ComputeTF(pat, M, TF)

	For i = 0 To N - 1
		state = TF(state, AscW(str(i)))

		If state = M Then
			retVal.Add(i - M + 1)
		End If
	Next

	Return retVal.ToArray()
End Function

Private Shared Function GetNextState(pat As String, M As Integer, state As Integer, x As Integer) As Integer
	If state < M AndAlso x = AscW(pat(state)) Then
		Return state + 1
	End If

	Dim ns As Integer, i As Integer

	For ns = state To 1 Step -1
		If AscW(pat(ns - 1)) = x Then
			For i = 0 To ns - 2
				If pat(i) <> pat(state - ns + 1 + i) Then
					Exit For
				End If
			Next

			If i = ns - 1 Then
				Return ns
			End If
		End If
	Next

	Return 0
End Function

Private Shared Sub ComputeTF(pat As String, M As Integer, TF As Integer(,))
	Dim state As Integer, x As Integer

	For state = 0 To M
		For x = 0 To 255
			TF(state, x) = GetNextState(pat, M, state, x)
		Next
	Next
End Sub
								

Example

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

Output

									0
31