Finite-State Automaton

Finite-State Automaton is a string searching algorithm.

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

									function SearchString($str, $pat)
{
	$retVal = array();
	$M = strlen($pat);
	$N = strlen($str);
	$state = 0;

	ComputeTF($pat, $M, $TF);

	for ($i = 0; $i < $N; $i++)
	{
		$state = $TF[$state][ord($str[$i])];

		if ($state == $M)
		{
			array_push($retVal, $i - $M + 1);
		}
	}

	return $retVal;
}

function ComputeTF($pat, $M, &$TF)
{
	for ($state = 0; $state <= $M; $state++)
		for ($x = 0; $x < 256; $x++)
			$TF[$state][$x] = GetNextState($pat, $M, $state, $x);
}

function GetNextState($pat, $M, $state, $x)
{
	if ($state < $M && $x == ord($pat[$state]))
		return $state + 1;

	for ($ns = $state; $ns > 0; $ns--)
	{
		if (ord($pat[$ns - 1]) == $x)
		{
			for ($i = 0; $i < $ns - 1; $i++)
			{
				if (ord($pat[$i]) != ord($pat[$state - $ns + 1 + $i]))
					break;
			}

			if ($i == $ns - 1)
				return $ns;
		}
	}

	return 0;
}
								

Example

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

Output

									0
31