Longest Common Substring

Longest common substring is an algorithm that finds the longest string that is a substring of two or more strings.

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

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

static int LongestCommonSubstring(const string& str1, const string& str2, string &subStr) {
	subStr = "";

	if (str1.empty() || str2.empty())
	{
		return 0;
	}

	int *curr = new int[str2.size()];
	int *prev = new int[str2.size()];
	int *swap = nullptr;
	int maxSubstr = 0;
	int lastSubsBegin = 0;
	string sequenceBuilder;

	for (int i = 0; i<str1.size(); ++i)
	{
		for (int j = 0; j<str2.size(); ++j)
		{
			if (str1[i] != str2[j])
			{
				curr[j] = 0;
			}
			else
			{
				if (i == 0 || j == 0)
				{
					curr[j] = 1;
				}
				else
				{
					curr[j] = 1 + prev[j - 1];
				}

				if (maxSubstr < curr[j])
				{
					maxSubstr = curr[j];

					int thisSubsBegin = i - curr[j] + 1;
					if (lastSubsBegin == thisSubsBegin)
					{
						sequenceBuilder += str1[i];
					}
					else
					{
						lastSubsBegin = thisSubsBegin;
						sequenceBuilder = "";
						sequenceBuilder += str1.substr(lastSubsBegin, (i + 1) - lastSubsBegin);;
					}
				}
			}
		}
		swap = curr;
		curr = prev;
		prev = swap;
	}

	delete[] curr;
	delete[] prev;

	subStr = sequenceBuilder;

	return maxSubstr;
}

Example

									string str1 = "the quick brown fox jumps over the lazy dog";
string str2 = "ghdsgf fjsdfg ghdsfbrown fox jumpshfsdjfg 457877fsdfhb$%";
string value;
int maxSubstr = LongestCommonSubstring(str1, str2, value);

Output

									brown fox jumps