# 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`
```