За последние 24 часа нас посетили 20723 программиста и 1106 роботов. Сейчас ищут 475 программистов ...

LCS наибольшая общая подпоследовательность

Тема в разделе "PHP для профи", создана пользователем johovich, 19 ноя 2018.

Метки:
  1. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    Потребовалось получать самую длинную общую часть 2 строк. Поковырялся и нашел хитрый вариант реализации, но очень уж медленный.

    Оказалось, что это классическая задача в программировании. Якобы самый быстрый способ через некое динамическое программирование. Что это?

    Предлагаю Вам размять немного мозг и сделать свою хорошую реализацию данной функции.
    Я запилил свою, завтра выложу.
     
  2. nospiou

    nospiou Старожил

    С нами с:
    4 фев 2018
    Сообщения:
    3.400
    Симпатии:
    510
  3. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    Не смотрел код, посмотрел тесты. Может такой LCS и каноничный. Но это не то. Неправильно назвал тему видимо.
    В таком примере софт по твоей ссылке даст 2 слово в качестве общей подпоследовательности.
    ABCD
    AD
    ABD

    Должно быть просто D

    Наверное это правильно назвать наибольшая общая подстрока.
     

    Вложения:

  4. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    PHP:
    1. function lcs2($first, $second)
    2. {
    3.     $len1 = strlen($first);
    4.     $len2 = strlen($second);
    5.     $needle = '';
    6.  
    7.     if($len1 < $len2){
    8.         $shortest = $first;
    9.         $longest = $second;
    10.         $len_short = $len1;
    11.     } else{
    12.         $shortest = $second;
    13.         $longest = $first;
    14.         $len_short = $len2;
    15.     }
    16.  
    17.  
    18.     for($i = 0; $i < $len_short; ++$i){
    19.         for($j = $len_short; $j > 0; --$j){
    20.             $needle = substr($shortest, $i, $j);
    21.             $pos = strpos($longest, $needle);
    22.             if($pos !== false) {
    23.                 break 2;
    24.             }
    25.         }
    26.     }
    27.     return substr($longest, $pos, strlen($needle));
    28. }
     
  5. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    Предыдущая кривая получилась.

    Вот две рабочие функции:
    PHP:
    1. function lcs2($first, $second)
    2. {
    3.     $len1 = strlen($first);
    4.     $len2 = strlen($second);
    5.  
    6.     if ($len1 < $len2) {
    7.         $shortest = $first;
    8.         $longest = $second;
    9.         $len_shortest = $len1;
    10.     } else {
    11.         $shortest = $second;
    12.         $longest = $first;
    13.         $len_shortest = $len2;
    14.     }
    15.  
    16.     //check max len
    17.     $pos = strpos($longest, $shortest);
    18.     if($pos !== false) return $shortest;
    19.  
    20.     for ($i = 1, $j = $len_shortest - 1; $j > 0; --$j, ++$i) {
    21.         for($k = 0; $k <= $i; ++$k){
    22.             $substr = substr($shortest, $k, $j);
    23.             $pos = strpos($longest, $substr);
    24.             if($pos !== false) return $substr;
    25.         }
    26.     }
    27.  
    28.     return "";
    29. }
    30.  
    31. function lcs3($string1, $string2)
    32. {
    33.     $L = array();
    34.     $length = 0;
    35.     $pos = 0;
    36.     $array1 = str_split($string1);
    37.     $array2 = str_split($string2);
    38.     foreach ($array1 as $i => $c1) {
    39.         $L[$i] = array();
    40.         foreach ($array2 as $j => $c2) {
    41.             $L[$i][$j] = 0;
    42.             if ($c1 == $c2) {
    43.                 if ($i == 0 || $j == 0) {
    44.                     // initialize that this character position exists.
    45.                     $L[$i][$j] = 1;
    46.                 } else {
    47.                     // increment previous or reset.
    48.                     if (isset($L[$i - 1][$j - 1])) {
    49.                         $L[$i][$j] = $L[$i - 1][$j - 1] + 1;
    50.                     } else {
    51.                         $L[$i][$j] = 0;
    52.                     }
    53.                 }
    54.                 if ($L[$i][$j] > $length) {
    55.                     $length = $L[$i][$j];
    56.                 }
    57.                 if ((isset($L[$i][$j])) && ($L[$i][$j] == $length)) {
    58.                     $pos = $i;
    59.                 }
    60.             }
    61.         }
    62.     }
    63.     if ($length > 0) {
    64.         return substr($string1, $pos - $length + 1, $length);
    65.     } else {
    66.         return '';
    67.     }
    68. }
    --- Добавлено ---
    Мультибайтовый вариант моей функции.
    PHP:
    1. function lcs2($first, $second)
    2. {
    3.     $len1 = strlen($first);
    4.     $len2 = strlen($second);
    5.  
    6.     if ($len1 < $len2) {
    7.         $shortest = $first;
    8.         $longest = $second;
    9.         $len_shortest = $len1;
    10.     } else {
    11.         $shortest = $second;
    12.         $longest = $first;
    13.         $len_shortest = $len2;
    14.     }
    15.  
    16.     //check max len
    17.     $pos = strpos($longest, $shortest);
    18.     if($pos !== false) return $shortest;
    19.  
    20.     for ($i = 1, $j = $len_shortest - 1; $j > 0; --$j, ++$i) {
    21.         for($k = 0; $k <= $i; ++$k){
    22.             $substr = substr($shortest, $k, $j);
    23.             $pos = strpos($longest, $substr);
    24.             //if found then check last char if it is > 128 then trim it
    25.             if($pos !== false) return ord($substr[$j-1]) > 128 ? substr($substr, 0, $j - 1) : $substr;
    26.         }
    27.     }
    28.  
    29.     return "";
    30. }