note 22900 deleted from ref.strings by maxim
| From: | maxim@php.net | Date: | Tue, 12 Nov 2002 16:23:38 +0000 |
| Subject: | note 22900 deleted from ref.strings by maxim | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-39399@lists.php.net to get a copy of this message | ||
Earlier I posted a LongestCommonSubstring function. The function does not find the long common
CONTIGUOUS substring, so I've modified it to do that, in case anyone needs it:
function LongestCommonContiguousSubstring($string1, $string2)
{
// find length of longest common substring first
$L = array();
$length1 = strlen($string1);
$length2 = strlen($string2);
for ($i = $length1; $i >= 0; $i--)
{
for ($j = $length2; $j >= 0; $j--)
{
if ($string1[$i] == '' || $string2[$j] == '') $L[$i][$j] = 0;
elseif ($string1[$i] == $string2[$j]) $L[$i][$j] = 1 + $L[$i+1][$j+1];
else $L[$i][$j] = max($L[$i + 1][$j], $L[$i][$j + 1]);
}
}
// then find the actual substring
$substrings = array();
$i = 0;
$j = 0;
$s = 0;
while ($i < $length1 && $j < $length2)
{
if ($string1[$i] == $string2[$j])
{
$substrings[$s] .= $string1[$i];
$i++; $j++;
continue;
}
elseif ($L[$i + 1][$j] >= $L[$i][$j + 1]) $i++;
else $j++;
$s++;
}
$maxlength = 0;
while (list($key, $val) = each($substrings))
{
$length = strlen($val);
if ($length > $maxlength)
{
$maxlength = $length;
$winner = $key;
}
}
return $substrings[$winner];
}