найти общий префикс массива строк

Question

У меня есть такой массив:

$sports = array(
'Softball - Counties',
'Softball - Eastern',
'Softball - North Harbour',
'Softball - South',
'Softball - Western'
);

Я хотел бы найти самый длинный общий префикс строки. В этом случае это будет 'Softball - '

Я думаю, что буду следовать этому процессу

$i = 1;

// loop to the length of the first string
while ($i < strlen($sports[0]) {

  // grab the left most part up to i in length
  $match = substr($sports[0], 0, $i);

  // loop through all the values in array, and compare if they match
  foreach ($sports as $sport) {

     if ($match != substr($sport, 0, $i) {
         // didn't match, return the part that did match
         return substr($sport, 0, $i-1);
     }

  } // foreach

   // increase string length
   $i++;
} // while

// if you got to here, then all of them must be identical

Вопросы

1. Есть ли встроенная функция или гораздо более простой способ сделать это?

2. Для моего 5-строчного массива это, вероятно, хорошо, но если бы я сделал несколько тысяч строковых массивов, было бы много накладных расходов, поэтому мне пришлось бы рассчитывать перемещение с моими начальными значениями $i, например, $i = половина строки, если она не работает, то $i/2, пока она не заработает, затем увеличивайте $i на 1, пока мы не добьемся успеха. Так что мы делаем наименьшее количество сравнений, чтобы получить результат.

Существует ли уже формула / алгоритм для решения этой проблемы?

Answer 1

Это дополнение к ответу @Gumbo. Если вы хотите убедиться, что выбранный общий префикс не разбивает слова, используйте это. Я просто заставляю его искать пустое место в конце выбранной строки. Если это существует, мы знаем, что было больше для всех фраз, поэтому мы усекаем это.

function product_name_intersection($array){

    $pl = 0; // common prefix length
    $n = count($array);
    $l = strlen($array[0]);
    $first = current($array);

    while ($pl < $l) {
        $c = $array[0][$pl];
        for ($i=1; $i<$n; $i++) {
            if (!isset($array[$i][$pl]) || $array[$i][$pl] !== $c) break 2;
        }
        $pl++;
    }
    $prefix = substr($array[0], 0, $pl);

    if ($pl < strlen($first) && substr($prefix, -1, 1) != ' ') {

        $prefix = preg_replace('/\W\w+\s*(\W*)$/', '$1', $prefix);
    }

    $prefix =  preg_replace('/^\W*(.+?)\W*$/', '$1', $prefix);

    return $prefix;
}

Answer 2

Для чего это стоит, вот еще одна альтернатива, которую я придумал.

Я использовал это для поиска общего префикса для списка кодов продуктов (т. Е. Там, где есть несколько SKU продуктов, у которых в начале есть общая серия символов):

/**
 * Try to find a common prefix for a list of strings
 * 
 * @param array $strings
 * @return string
 */
function findCommonPrefix(array $strings)
{
    $prefix = '';
    $chars = array_map("str_split", $strings);
    $matches = call_user_func_array("array_intersect_assoc", $chars);
    if ($matches) {
        $i = 0;
        foreach ($matches as $key => $value) {
            if ($key != $i) {
                unset($matches[$key]);
            }
            $i++;
        }
        $prefix = join('', $matches);
    }

    return $prefix;
}

Answer 3

Верхний ответ казался немного длинным, поэтому вот краткое решение с временем выполнения O (n ² ).

function findLongestPrefix($arr) {
  return array_reduce($arr, function($prefix, $item) {
    $length = min(strlen($prefix), strlen($item));
    while (substr($prefix, 0, $length) !== substr($item, 0, $length)) {
      $length--;
    }
    return substr($prefix, 0, $length);
  }, $arr[0]);
}

print findLongestPrefix($sports); // Softball -

Answer 4

Решения здесь работают только для нахождения общих черт в начале строк. Вот функция, которая ищет самую длинную общую подстроку в любом месте в массиве строк.

http://www.christopherbloom.com/2011/02/24/find-the-longest-common-substring-using-php/

Answer 5

    // Common prefix
    $common = '';

    $sports = array(
    'Softball T - Counties',
    'Softball T - Eastern',
    'Softball T - North Harbour',
    'Softball T - South',
    'Softball T - Western'
    );

    // find mini string
    $minLen = strlen($sports[0]);
    foreach ($sports as $s){
        if($minLen > strlen($s))
            $minLen = strlen($s);
    }


    // flag to break out of inner loop
    $flag = false;

    // The possible common string length does not exceed the minimum string length.
    // The following solution is O(n^2), this can be improve.
    for ($i = 0 ; $i < $minLen; $i++){
        $tmp = $sports[0][$i];

        foreach ($sports as $s){
            if($s[$i] != $tmp)
                $flag = true;
        }
        if($flag)
            break;
        else
            $common .= $sports[0][$i];
    }

    print $common;

Answer 6

Я бы использовал рекурсивный алгоритм, подобный этому:

1 - получить первую строку в массиве 2 - вызвать метод рекурсивного префикса с первой строкой в ​​качестве параметра 3 - если префикс пуст, вернуть не префикс 4 - перебрать все строки в массиве 4.1 - если любая из строк не начинается с префикса 4.1.1 - вызов метода рекурсивного префикса с префиксом - 1 в качестве параметра 4.2 обратный префикс

Answer 7

@ bumperbox

1. Ваш базовый код нуждался в некоторой коррекции для работы во ВСЕХ сценариях!

   • Ваш цикл сравнивается только до одного символа перед последним символом!
   • Несоответствие может произойти через 1 цикл после последнего общего символа.
   • Следовательно, вы должны по крайней мере проверять до 1 символа после последнего символа вашей первой строки.
   • Следовательно, ваш оператор сравнения должен быть "<= 1" или "<2". </li>

2. В настоящее время ваш алгоритм не работает

   • если первая строка полностью включена во все остальные строки,
   • или полностью включено во все остальные строки, кроме последнего символа.

В своем следующем ответе / посте я приложу код, оптимизированный для итераций!

Оригинальный код Bumperbox PLUS, исправление (PHP):

function shortest($sports) {
 $i = 1;

 // loop to the length of the first string
 while ($i < strlen($sports[0])) {

  // grab the left most part up to i in length
  // REMARK: Culturally biased towards LTR writing systems. Better say: Grab frombeginning...
  $match = substr($sports[0], 0, $i);

  // loop through all the values in array, and compare if they match
  foreach ($sports as $sport) {
   if ($match != substr($sport, 0, $i)) {
    // didn't match, return the part that did match
    return substr($sport, 0, $i-1);
   }
  }
 $i++; // increase string length
 }
}

function shortestCorrect($sports) {
 $i = 1;
 while ($i <= strlen($sports[0]) + 1) {
  // Grab the string from its beginning with length $i
  $match = substr($sports[0], 0, $i);
  foreach ($sports as $sport) {
   if ($match != substr($sport, 0, $i)) {
    return substr($sport, 0, $i-1);
   }
  }
  $i++;
 }
 // Special case: No mismatch happened until loop end! Thus entire str1 is common prefix!
 return $sports[0];
}

$sports1 = array(
'Softball',
'Softball - Eastern',
'Softball - North Harbour');

$sports2 = array(
'Softball - Wester',
'Softball - Western',
);

$sports3 = array(
'Softball - Western',
'Softball - Western',
);

$sports4 = array(
'Softball - Westerner',
'Softball - Western',
);

echo("Output of the original function:\n"); // Failure scenarios

var_dump(shortest($sports1)); // NULL rather than the correct 'Softball'
var_dump(shortest($sports2)); // NULL rather than the correct 'Softball - Wester'
var_dump(shortest($sports3)); // NULL rather than the correct 'Softball - Western'
var_dump(shortest($sports4)); // Only works if the second string is at least one character longer!

echo("\nOutput of the corrected function:\n"); // All scenarios work
var_dump(shortestCorrect($sports1));
var_dump(shortestCorrect($sports2));
var_dump(shortestCorrect($sports3));
var_dump(shortestCorrect($sports4));