Longest Common Substring

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

									public static int LongestCommonSubstring(string str1, string str2, out string subStr)
{
	subStr = string.Empty;

	if (string.IsNullOrEmpty(str1) || string.IsNullOrEmpty(str2))
		return 0;

	int[,] num = new int[str1.Length, str2.Length];
	int maxlen = 0;
	int lastSubsBegin = 0;
	StringBuilder subStrBuilder = new StringBuilder();

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

				if (num[i, j] > maxlen)
				{
					maxlen = num[i, j];

					int thisSubsBegin = i - num[i, j] + 1;

					if (lastSubsBegin == thisSubsBegin)
					{
						subStrBuilder.Append(str1[i]);
					}
					else
					{
						lastSubsBegin = thisSubsBegin;
						subStrBuilder.Length = 0;
						subStrBuilder.Append(str1.Substring(lastSubsBegin, (i + 1) - lastSubsBegin));
					}
				}
			}
		}
	}

	subStr = subStrBuilder.ToString();

	return maxlen;
}

Example

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

Output

									brown fox jumps