Longest Common Substring

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

• C#
• VB.Net
• C
• C++
• PHP

									function LongestCommonSubstring($str1, $str2, &$subStr)
{
	$subStr = "";

	if ($str1 == "" || $str2 == "")
		return 0;

	$num = array();
	$maxlen = 0;
	$lastSubsBegin = 0;
	$subStrBuilder = "";
	$str1Len = strlen($str1);
	$str2Len = strlen($str2);

	for ($i = 0; $i < $str1Len; $i++)
	{
		for ($j = 0; $j < $str2Len; $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];

					$thisSubsBegin = $i - $num[$i][$j] + 1;

					if ($lastSubsBegin == $thisSubsBegin)
					{
						$subStrBuilder .= $str1[$i];
					}
					else
					{
						$lastSubsBegin = $thisSubsBegin;
						$subStrBuilder = "";
						$subStrBuilder .= substr($str1, $lastSubsBegin, ($i + 1) - $lastSubsBegin);
					}
				}
			}
		}
	}

	$subStr = $subStrBuilder;

	return $maxlen;
}
								

Example

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

Output

									brown fox jumps