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*****/
// string
// algorithm
/***********************************************/

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

static int Min(int a, int b) {
	return a <= b ? a : b;
}

static string LongestCommonString(string a, string b) {
	int n = Min(a.length(), b.length());
	string result = "";

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

	return result;
}

static string LongestRepeatedSubstring(string str) {
	if (str.empty())
		return "";

	int N = str.length();
	string* substrings = new string[N];

	for (int i = 0; i < N; i++)
	{
		substrings[i] = str.substr(i);
	}

	std::sort(substrings, substrings + N);

	string result = "";

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

		if (lcs.length() > result.length())
		{
			result = lcs;
		}
	}

	delete[] substrings;

	return result;
}

Example

									string data = "the quick brown fox jumps over the lazy dog";
string value = LongestRepeatedSubstring(data);

Output

the