Finite-State Automaton

Finite-State Automaton is a string searching algorithm.

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

									/*****Please include following header files*****/
// string
// vector
/***********************************************/

/*****Please use following namespaces*****/
// std
/*****************************************/

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;
}

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);
}

static vector<int> SearchString(string str, string pat) {
	vector<int> retVal;
	int M = pat.length();
	int N = str.length();
	int i, state = 0;

	int** TF = new int*[M + 1];
	for (int i = 0; i < (M + 1); ++i)
		TF[i] = new int[256];

	ComputeTF(pat, M, TF);

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

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

	for (int i = 0; i < (M + 1); ++i)
		delete[] TF[i];

	delete[] TF;
	
	return retVal;
}
								

Example

									string data = "the quick brown fox jumps over the lazy dog";
vector<int> value = SearchString(data, "the");
								

Output

									0
31