Потребовалось получать самую длинную общую часть 2 строк. Поковырялся и нашел хитрый вариант реализации, но очень уж медленный. Оказалось, что это классическая задача в программировании. Якобы самый быстрый способ через некое динамическое программирование. Что это? Предлагаю Вам размять немного мозг и сделать свою хорошую реализацию данной функции. Я запилил свою, завтра выложу.
Не смотрел код, посмотрел тесты. Может такой LCS и каноничный. Но это не то. Неправильно назвал тему видимо. В таком примере софт по твоей ссылке даст 2 слово в качестве общей подпоследовательности. ABCD AD ABD Должно быть просто D Наверное это правильно назвать наибольшая общая подстрока.
PHP: function lcs2($first, $second) { $len1 = strlen($first); $len2 = strlen($second); $needle = ''; if($len1 < $len2){ $shortest = $first; $longest = $second; $len_short = $len1; } else{ $shortest = $second; $longest = $first; $len_short = $len2; } for($i = 0; $i < $len_short; ++$i){ for($j = $len_short; $j > 0; --$j){ $needle = substr($shortest, $i, $j); $pos = strpos($longest, $needle); if($pos !== false) { break 2; } } } return substr($longest, $pos, strlen($needle)); }
Предыдущая кривая получилась. Вот две рабочие функции: PHP: function lcs2($first, $second) { $len1 = strlen($first); $len2 = strlen($second); if ($len1 < $len2) { $shortest = $first; $longest = $second; $len_shortest = $len1; } else { $shortest = $second; $longest = $first; $len_shortest = $len2; } //check max len $pos = strpos($longest, $shortest); if($pos !== false) return $shortest; for ($i = 1, $j = $len_shortest - 1; $j > 0; --$j, ++$i) { for($k = 0; $k <= $i; ++$k){ $substr = substr($shortest, $k, $j); $pos = strpos($longest, $substr); if($pos !== false) return $substr; } } return ""; } function lcs3($string1, $string2) { $L = array(); $length = 0; $pos = 0; $array1 = str_split($string1); $array2 = str_split($string2); foreach ($array1 as $i => $c1) { $L[$i] = array(); foreach ($array2 as $j => $c2) { $L[$i][$j] = 0; if ($c1 == $c2) { if ($i == 0 || $j == 0) { // initialize that this character position exists. $L[$i][$j] = 1; } else { // increment previous or reset. if (isset($L[$i - 1][$j - 1])) { $L[$i][$j] = $L[$i - 1][$j - 1] + 1; } else { $L[$i][$j] = 0; } } if ($L[$i][$j] > $length) { $length = $L[$i][$j]; } if ((isset($L[$i][$j])) && ($L[$i][$j] == $length)) { $pos = $i; } } } } if ($length > 0) { return substr($string1, $pos - $length + 1, $length); } else { return ''; } } --- Добавлено --- Мультибайтовый вариант моей функции. PHP: function lcs2($first, $second) { $len1 = strlen($first); $len2 = strlen($second); if ($len1 < $len2) { $shortest = $first; $longest = $second; $len_shortest = $len1; } else { $shortest = $second; $longest = $first; $len_shortest = $len2; } //check max len $pos = strpos($longest, $shortest); if($pos !== false) return $shortest; for ($i = 1, $j = $len_shortest - 1; $j > 0; --$j, ++$i) { for($k = 0; $k <= $i; ++$k){ $substr = substr($shortest, $k, $j); $pos = strpos($longest, $substr); //if found then check last char if it is > 128 then trim it if($pos !== false) return ord($substr[$j-1]) > 128 ? substr($substr, 0, $j - 1) : $substr; } } return ""; }