Finite-State Automaton

Finite-State Automaton is a string searching algorithm.

									#define NO_OF_CHARS 256

int** Create2DArray(int rowCount, int colCount) {
	int* rArray = malloc(sizeof(int*) * rowCount);

	for (int i = 0; i < rowCount; i++) {
		rArray[i] = malloc(sizeof(int) * colCount);
	}

	return rArray;
}

void Delete2DArray(int** arr, int rowCount) {
	for (int i = 0; i < rowCount; i++) {
		free(arr[i]);
	}
}

int* AddItemInArray(int** arr, int count, int item) {
	int* newArr = malloc(sizeof(int) * (count + 1));

	for (int i = 0; i < count; i++) {
		newArr[i] = arr[i];
	}

	newArr[count] = item;

	return newArr;
}

int getNextState(char *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;
}

void computeTF(char *pat, int M, int** TF)
{
	int state, x;

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

int* SearchString(char* str, char* pat) {
	int* retVal = malloc(sizeof(int) * 1);
	int retValSize = 0;
	int M = strlen(pat);
	int N = strlen(str);
	int i, state = 0;

	int** TF = Create2DArray(M + 1, 256);

	computeTF(pat, M, TF);

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

		if (state == M)
		{
			retVal = AddItemInArray(retVal, retValSize++, i - M + 1);
		}
	}

	Delete2DArray(TF, M + 1);

	return retVal;
}

Example

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

Output

									0
31