Finite-State Automaton

Finite-State Automaton is a string searching algorithm.

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

									public static int[] SearchString(string str, string pat)
{
	List<int> retVal = new List<int>();
	int M = pat.Length;
	int N = str.Length;
	int i, state = 0;
	int[,] TF = new int[M + 1, 256];

	ComputeTF(pat, M, TF);

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

		if (state == M)
		{
			retVal.Add(i - M + 1);
		}
	}

	return retVal.ToArray();
}

private static void ComputeTF(string pat, int M, int[,] TF)
{
	int state, x;

	for (state = 0; state <= M; ++state)
		for (x = 0; x < 256; ++x)
			TF[state, x] = GetNextState(pat, M, state, x);
}

private static int GetNextState(string pat, int M, int state, int x)
{
	if (state < M && x == pat[state])
		return state + 1;

	int ns, i;

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

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

	return 0;
}
								

Example

									string data = "the quick brown fox jumps over the lazy dog";
int[] value = SearchString(data, "the");
								

Output

									0
31