note 22900 added to ref.strings
| From: | carl at _nospam_youngbloods dot org | Date: | Wed, 03 Jul 2002 16:14:40 +0000 |
| Subject: | note 22900 added to ref.strings | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-32554@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];
}
--
http://www.php.net/manual/en/ref.strings.php
http://master.php.net/manage/user-notes.php?action=edit+22900
http://master.php.net/manage/user-notes.php?action=delete+22900
http://master.php.net/manage/user-notes.php?action=reject+22900