Naive String Search Algorithm

Naive String Search is string searching algorithm. It is a simple but inefficient way to see where one string occurs inside another is to check each place it could be, one by one, to see if it's there.

									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* SearchString(char* str, char* pat) {
	int* retVal = malloc(sizeof(int));
	int retValSize = 0;
	int M = strlen(pat);
	int N = strlen(str);

	for (int i = 0; i <= N - M; i++)
	{
		int j;

		for (j = 0; j < M; j++)
		{
			if (str[i + j] != pat[j])
				break;
		}

		if (j == M)
			retVal = AddItemInArray(retVal, retValSize++, i);
	}

	return retVal;
}

Example

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

Output

									0
31