Longest Repeated Substring

Longest repeated substring is an algorithm that finds the longest substring of a string that occurs at least twice.

									/*****Please include following header files*****/
// stdlib.h
/***********************************************/

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

char* AppendString(const char* str1, const char* str2) {
	int str1Len = strlen(str1);
	int str2Len = strlen(str2);
	int strLen = str1Len + str2Len + 1;
	char* str = malloc(strLen);

	for (int i = 0; i < str1Len; i++)
		str[i] = str1[i];

	for (int i = 0; i < str2Len; i++)
		str[(str1Len + i)] = str2[i];

	str[strLen - 1] = '\0';

	return str;
}

char* GetSubString(char* str, int index, int count) {
	int strLen = strlen(str);
	int lastIndex = index + count;

	if (index >= 0 && lastIndex > strLen) return "";

	char* subStr = malloc(count + 1);

	for (int i = 0; i < count; i++) {
		subStr[i] = str[index + i];
	}

	subStr[count] = '\0';

	return subStr;
}


char* CharToString(char c) {
	char* str = malloc(2);
	str[0] = c;
	str[1] = '\0';

	return str;
}

char* LongestCommonString(char* a, char* b)
{
	int n = min(strlen(a), strlen(b));
	char* result = "";

	for (int i = 0; i < n; i++)
	{
		if (a[i] == b[i])
			result = AppendString(result, CharToString(a[i]));
		else
			break;
	}

	return result;
}

int Compare(const void * a, const void * b) {
	return strcmp(*(const char **)a, *(const char **)b);
}

char** Sort(char** str, int count) {
	char** s = Create2DArray(count, 1);

	int i;
	qsort(str, count, sizeof(const char *), Compare);
	for (i = 0; i < count; i++) {
		s[i] = str[i];
	}

	return s;
}

char* GetLongestRepeatedSubstring(char* str) {
	if (str == "")
		return "";

	int N = strlen(str);
	char** substrings = Create2DArray(N, 1);

	for (int i = 0; i < N; i++)
	{
		substrings[i] = GetSubString(str, i, N - i);
	}

	substrings = Sort(substrings, N);

	char* result = "";

	for (int i = 0; i < N - 1; i++)
	{
		char* lcs = LongestCommonString(substrings[i], substrings[i + 1]);

		if (strlen(lcs) > strlen(result))
		{
			result = lcs;
		}
	}

	free(substrings);

	return result;
}

Example

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

Output

the