Нахождение общего префикса массива строк

Ответ 1

Я реализовал алгоритм @diogoriba в коде, с этим результатом:

• Нахождение общего префикса первых двух строк, а затем сравнение этого со всеми следующими строками, начиная с 3-го, и обрезать общую строку, если ничего общего не найдено, выигрывает в ситуациях, когда в префиксах больше общего, чем разные.
• Но исходный алгоритм bumperbox (кроме исправлений) выигрывает, когда строки имеют меньше общего в их префиксе, чем другие. Подробности в комментариях кода!

Другая идея, которую я реализовал:

Сначала проверьте кратчайшую строку в массиве и используйте ее для сравнения, а не просто для первой строки. В коде это реализовано с помощью специальной письменной функции arrayStrLenMin().

• Можно резко сократить итерации, но функция arrayStrLenMin() может сама вызывать (более или менее) итерации.
• Просто начиная с длины первой строки в массиве кажется довольно неуклюжим, но может оказаться эффективным, если arrayStrLenMin() требует много итераций.

Получить максимальный общий префикс строк в массиве с минимальным количеством итераций (PHP)

Код + расширенное тестирование + Примечания:

function arrayStrLenMin ($arr, $strictMode = false, $forLoop = false) {
    $errArrZeroLength = -1; // Return value for error: Array is empty
    $errOtherType = -2;     // Return value for error: Found other type (than string in array)
    $errStrNone = -3;       // Return value for error: No strings found (in array)

    $arrLength = count($arr);
    if ($arrLength <= 0 ) { return $errArrZeroLength; }
    $cur = 0;

    foreach ($arr as $key => $val) {
        if (is_string($val)) {
            $min = strlen($val);
            $strFirstFound = $key;
            // echo("Key\tLength / Notification / Error\n");
            // echo("$key\tFound first string member at key with length: $min!\n");
            break;
        }
        else if ($strictMode) { return $errOtherType; } // At least 1 type other than string was found.
    }
    if (! isset($min)) { return $errStrNone; } // No string was found in array.

    // SpeedRatio of foreach/for is approximately 2/1 as dicussed at:
    // http://juliusbeckmann.de/blog/php-foreach-vs-while-vs-for-the-loop-battle.html

    // If $strFirstFound is found within the first 1/SpeedRatio (=0.5) of the array, "foreach" is faster!

    if (! $forLoop) {
        foreach ($arr as $key => $val) {
            if (is_string($val)) {
                $cur = strlen($val);
                // echo("$key\t$cur\n");
                if ($cur == 0) { return $cur; } // 0 is the shortest possible string, so we can abort here.
                if ($cur < $min) { $min = $cur; }
            }
        // else { echo("$key\tNo string!\n"); }
        }
    }

    // If $strFirstFound is found after the first 1/SpeedRatio (=0.5) of the array, "for" is faster!

    else {
        for ($i = $strFirstFound + 1; $i < $arrLength; $i++) {
            if (is_string($arr[$i])) {
                $cur = strlen($arr[$i]);
                // echo("$i\t$cur\n");
                if ($cur == 0) { return $cur; } // 0 is the shortest possible string, so we can abort here.
                if ($cur < $min) { $min = $cur; }
            }
            // else { echo("$i\tNo string!\n"); }
        }
    }

    return $min;
}

function strCommonPrefixByStr($arr, $strFindShortestFirst = false) {
    $arrLength = count($arr);
    if ($arrLength < 2) { return false; }

    // Determine loop length
    /// Find shortest string in array: Can bring down iterations dramatically, but the function arrayStrLenMin() itself can cause ( more or less) iterations.
    if ($strFindShortestFirst) { $end = arrayStrLenMin($arr, true); }
    /// Simply start with length of first string in array: Seems quite clumsy, but may turn out effective, if arrayStrLenMin() needs many iterations.
    else { $end = strlen($arr[0]); }

    for ($i = 1; $i <= $end + 1; $i++) {
        // Grab the part from 0 up to $i
        $commonStrMax = substr($arr[0], 0, $i);
        echo("Match: $i\t$commonStrMax\n");
        // Loop through all the values in array, and compare if they match
        foreach ($arr as $key => $str) {
            echo("  Str: $key\t$str\n");
            // Didn't match, return the part that did match
            if ($commonStrMax != substr($str, 0, $i)) {
                    return substr($commonStrMax, 0, $i-1);
            }
        }
    }
    // Special case: No mismatch (hence no return) happened until loop end!
    return $commonStrMax; // Thus entire first common string is the common prefix!
}

function strCommonPrefixByChar($arr, $strFindShortestFirst = false) {
    $arrLength = count($arr);
    if ($arrLength < 2) { return false; }

    // Determine loop length
    /// Find shortest string in array: Can bring down iterations dramatically, but the function arrayStrLenMin() itself can cause ( more or less) iterations.
    if ($strFindShortestFirst) { $end = arrayStrLenMin($arr, true); }
    /// Simply start with length of first string in array: Seems quite clumsy, but may turn out effective, if arrayStrLenMin() needs many iterations.
    else { $end = strlen($arr[0]); }

    for ($i = 0 ; $i <= $end + 1; $i++) {
        // Grab char $i
        $char = substr($arr[0], $i, 1);
        echo("Match: $i\t"); echo(str_pad($char, $i+1, " ", STR_PAD_LEFT)); echo("\n");
        // Loop through all the values in array, and compare if they match
        foreach ($arr as $key => $str) {
            echo("  Str: $key\t$str\n");
            // Didn't match, return the part that did match
            if ($char != $str[$i]) { // Same functionality as ($char != substr($str, $i, 1)). Same efficiency?
                    return substr($arr[0], 0, $i);
            }
        }
    }
    // Special case: No mismatch (hence no return) happened until loop end!
    return substr($arr[0], 0, $end); // Thus entire first common string is the common prefix!
}


function strCommonPrefixByNeighbour($arr) {
    $arrLength = count($arr);
    if ($arrLength < 2) { return false; }

    /// Get the common string prefix of the first 2 strings
    $strCommonMax = strCommonPrefixByChar(array($arr[0], $arr[1]));
    if ($strCommonMax === false) { return false; }
    if ($strCommonMax == "") { return ""; }
    $strCommonMaxLength = strlen($strCommonMax);

    /// Now start looping from the 3rd string
    echo("-----\n");
    for ($i = 2; ($i < $arrLength) && ($strCommonMaxLength >= 1); $i++ ) {
        echo("  STR: $i\t{$arr[$i]}\n");

        /// Compare the maximum common string with the next neighbour

        /*
        //// Compare by char: Method unsuitable!

        // Iterate from string end to string beginning
        for ($ii = $strCommonMaxLength - 1; $ii >= 0; $ii--) {
            echo("Match: $ii\t"); echo(str_pad($arr[$i][$ii], $ii+1, " ", STR_PAD_LEFT)); echo("\n");
            // If you find the first mismatch from the end, break.
            if ($arr[$i][$ii] != $strCommonMax[$ii]) {
                $strCommonMaxLength = $ii - 1; break;
                // BUT!!! We may falsely assume that the string from the first mismatch until the begining match! This new string neighbour string is completely "unexplored land", there might be differing chars closer to the beginning. This method is not suitable. Better use string comparison than char comparison.
            }
        }
        */

        //// Compare by string

        for ($ii = $strCommonMaxLength; $ii > 0; $ii--) {
            echo("MATCH: $ii\t$strCommonMax\n");
            if (substr($arr[$i],0,$ii) == $strCommonMax) {
                break;
            }
            else {
                $strCommonMax = substr($strCommonMax,0,$ii - 1);
                $strCommonMaxLength--;
            }
        }
    }
    return substr($arr[0], 0, $strCommonMaxLength);
}





// Tests for finding the common prefix

/// Scenarios

$filesLeastInCommon = array (
"/Vol/1/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/a/1",
"/Vol/2/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/a/2",
"/Vol/1/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/b/1",
"/Vol/1/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/b/2",
"/Vol/2/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/b/c/1",
"/Vol/2/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/a/1",
);

$filesLessInCommon = array (
"/Vol/1/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/a/1",
"/Vol/1/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/a/2",
"/Vol/1/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/b/1",
"/Vol/1/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/b/2",
"/Vol/2/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/b/c/1",
"/Vol/2/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/a/1",
);

$filesMoreInCommon = array (
"/Voluuuuuuuuuuuuuumes/1/a/a/1",
"/Voluuuuuuuuuuuuuumes/1/a/a/2",
"/Voluuuuuuuuuuuuuumes/1/a/b/1",
"/Voluuuuuuuuuuuuuumes/1/a/b/2",
"/Voluuuuuuuuuuuuuumes/2/a/b/c/1",
"/Voluuuuuuuuuuuuuumes/2/a/a/1",
);

$sameDir = array (
"/Volumes/1/a/a/",
"/Volumes/1/a/a/aaaaa/2",
);

$sameFile = array (
"/Volumes/1/a/a/1",
"/Volumes/1/a/a/1",
);

$noCommonPrefix = array (
"/Volumes/1/a/a/",
"/Volumes/1/a/a/aaaaa/2",
"Net/1/a/a/aaaaa/2",
);

$longestLast = array (
"/Volumes/1/a/a/1",
"/Volumes/1/a/a/aaaaa/2",
);

$longestFirst = array (
"/Volumes/1/a/a/aaaaa/1",
"/Volumes/1/a/a/2",
);

$one = array ("/Volumes/1/a/a/aaaaa/1");

$empty = array ( );


// Test Results for finding  the common prefix

/*

I tested my functions in many possible scenarios.
The results, the common prefixes, were always correct in all scenarios!
Just try a function call with your individual array!

Considering iteration efficiency, I also performed tests:

I put echo functions into the functions where iterations occur, and measured the number of CLI line output via:
php <script with strCommonPrefixByStr or strCommonPrefixByChar> | egrep "^  Str:" | wc -l   GIVES TOTAL ITERATION SUM.
php <Script with strCommonPrefixByNeighbour> | egrep "^  Str:" | wc -l   PLUS   | egrep "^MATCH:" | wc -l   GIVES TOTAL ITERATION SUM.

My hypothesis was proven:
strCommonPrefixByChar wins in situations where the strings have less in common in their beginning (=prefix).
strCommonPrefixByNeighbour wins where there is more in common in the prefixes.

*/

// Test Results Table
// Used Functions | Iteration amount | Remarks

// $result = (strCommonPrefixByStr($filesLessInCommon)); // 35
// $result = (strCommonPrefixByChar($filesLessInCommon)); // 35 // Same amount of iterations, but much fewer characters compared because ByChar instead of ByString!
// $result = (strCommonPrefixByNeighbour($filesLessInCommon)); // 88 + 42 = 130 // Loses in this category!

// $result = (strCommonPrefixByStr($filesMoreInCommon)); // 137
// $result = (strCommonPrefixByChar($filesMoreInCommon)); // 137 // Same amount of iterations, but much fewer characters compared because ByChar instead of ByString!
// $result = (strCommonPrefixByNeighbour($filesLeastInCommon)); // 12 + 4 = 16 // Far the winner in this category!

echo("Common prefix of all members:\n");
var_dump($result);





// Tests for finding the shortest string in array

/// Arrays

// $empty = array ();
// $noStrings = array (0,1,2,3.0001,4,false,true,77);
// $stringsOnly = array ("one","two","three","four");
// $mixed = array (0,1,2,3.0001,"four",false,true,"seven", 8888);

/// Scenarios

// I list them from fewest to most iterations, which is not necessarily equivalent to slowest to fastest!
// For speed consider the remarks in the code considering the Speed ratio of foreach/for!

//// Fewest iterations (immediate abort on "Found other type", use "for" loop)

// foreach( array($empty, $noStrings, $stringsOnly, $mixed) as $arr) {
//  echo("NEW ANALYSIS:\n");
//  echo("Result: " . arrayStrLenMin($arr, true, true) . "\n\n");
// }

/* Results:

    NEW ANALYSIS:
    Result: Array is empty!

    NEW ANALYSIS:
    Result: Found other type!

    NEW ANALYSIS:
    Key Length / Notification / Error
    0   Found first string member at key with length: 3!
    1   3
    2   5
    3   4
    Result: 3

    NEW ANALYSIS:
    Result: Found other type!

*/

//// Fewer iterations (immediate abort on "Found other type", use "foreach" loop)

// foreach( array($empty, $noStrings, $stringsOnly, $mixed) as $arr) {
//  echo("NEW ANALYSIS:\n");
//  echo("Result: " . arrayStrLenMin($arr, true, false) . "\n\n");
// }

/* Results:

    NEW ANALYSIS:
    Result: Array is empty!

    NEW ANALYSIS:
    Result: Found other type!

    NEW ANALYSIS:
    Key Length / Notification / Error
    0   Found first string member at key with length: 3!
    0   3
    1   3
    2   5
    3   4
    Result: 3

    NEW ANALYSIS:
    Result: Found other type!

*/

//// More iterations (No immediate abort on "Found other type", use "for" loop)

// foreach( array($empty, $noStrings, $stringsOnly, $mixed) as $arr) {
//  echo("NEW ANALYSIS:\n");
//  echo("Result: " . arrayStrLenMin($arr, false, true) . "\n\n");
// }

/* Results:

    NEW ANALYSIS:
    Result: Array is empty!

    NEW ANALYSIS:
    Result: No strings found!

    NEW ANALYSIS:
    Key Length / Notification / Error
    0   Found first string member at key with length: 3!
    1   3
    2   5
    3   4
    Result: 3

    NEW ANALYSIS:
    Key Length / Notification / Error
    4   Found first string member at key with length: 4!
    5   No string!
    6   No string!
    7   5
    8   No string!
    Result: 4

*/


//// Most iterations (No immediate abort on "Found other type", use "foreach" loop)

// foreach( array($empty, $noStrings, $stringsOnly, $mixed) as $arr) {
//  echo("NEW ANALYSIS:\n");
//  echo("Result: " . arrayStrLenMin($arr, false, false) . "\n\n");
// }

/* Results:

    NEW ANALYSIS:
    Result: Array is empty!

    NEW ANALYSIS:
    Result: No strings found!

    NEW ANALYSIS:
    Key Length / Notification / Error
    0   Found first string member at key with length: 3!
    0   3
    1   3
    2   5
    3   4
    Result: 3

    NEW ANALYSIS:
    Key Length / Notification / Error
    4   Found first string member at key with length: 4!
    0   No string!
    1   No string!
    2   No string!
    3   No string!
    4   4
    5   No string!
    6   No string!
    7   5
    8   No string!
    Result: 4

*/

Ответ 2

Я бы использовал это:

$prefix = array_shift($array);  // take the first item as initial prefix
$length = strlen($prefix);
// compare the current prefix with the prefix of the same length of the other items
foreach ($array as $item) {
    // check if there is a match; if not, decrease the prefix by one character at a time
    while ($length && substr($item, 0, $length) !== $prefix) {
        $length--;
        $prefix = substr($prefix, 0, -1);
    }
    if (!$length) {
        break;
    }
}

Обновление Heres другое решение, итеративное сравнение каждого n-го символа строк до тех пор, пока не будет обнаружено несоответствие:

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

Это еще более эффективно, так как существует только самое большее число атомных сравнений numberOfStrings · commonPrefixLength.

Ответ 3

Вероятно, для этого есть какой-то ужасно известный алгоритм, но только с моей головы, если вы знаете, что ваша общность будет с левой стороны, как в вашем примере, вы могли бы сделать лучше, чем ваша опубликованная методология, сначала обнаруживая общность первых двух строк, а затем итерируя остальную часть списка, обрезая общую строку по мере необходимости, чтобы добиться общности или прекращения с ошибкой, если вы полностью обрезаете ничего.

Ответ 4

Думаю, ты на правильном пути. Но вместо того, чтобы увеличивать i, когда вся строка проходит, вы можете сделать это:

1) Сравните первые 2 строки в массиве и узнайте, сколько общих символов у них есть. Сохраните общие символы в отдельной строке, называемой maxCommon, например.

2) Сравните третью строку w/maxCommon. Если количество общих символов меньше, обведите maxCommon символам, которые соответствуют.

3) Повторите и промойте оставшуюся часть массива. В конце процесса maxCommon будет иметь строку, которая является общей для всех элементов массива.

Это добавит некоторые накладные расходы, потому что вам нужно будет сравнить каждую строку w/maxCommon, но резко сократит количество итераций, которые вам понадобятся для получения ваших результатов.

Ответ 5

Если вы можете сортировать свой массив, то есть простое и очень быстрое решение.

Просто сравните первый элемент с последним.

Если строки отсортированы, любой префикс, общий для всех строк, будет общим для отсортированных первой и последней строк.

sort($sport);

$s1 = $sport[0];               // First string
$s2 = $sport[count($sport)-1]; // Last string
$len = min(strlen($s1), strlen($s2));

// While we still have string to compare,
// if the indexed character is the same in both strings,
// increment the index. 
for ($i=0; $i<$len && $s1[$i]==$s2[$i]; $i++); 

$prefix = substr($s1, 0, $i);

Ответ 6

Я предполагаю, что под "общей частью" вы подразумеваете "самый длинный общий префикс". Это намного проще вычислять, чем любая общая подстрока.

Это не может быть сделано без чтения символов (n+1) * m в худшем случае и n * m + 1 в лучшем случае, где n - длина самого длинного общего префикса, а m - количество строк.

Сравнение одной буквы за раз достигает такой эффективности (Большая Тета (n * m)).

Ваш предложенный алгоритм работает в Big Theta (n ^ 2 * m), что намного, намного медленнее для больших входов.

Третий предложенный алгоритм нахождения самого длинного префикса первых двух строк, а затем сравнение с третьим, четвертым и т.д. также имеет время работы в Большой тете (n * m), но с более высоким постоянным множителем. Вероятно, на практике это будет немного медленнее.

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

Посмотрите WikiPedia для описания нотации Big Theta.

Ответ 7

Здесь изящная, рекурсивная реализация в JavaScript:

function prefix(strings) {
    switch (strings.length) {

      case 0:
        return "";

      case 1:
        return strings[0];

      case 2:
        // compute the prefix between the two strings
        var a = strings[0],
            b = strings[1],
            n = Math.min(a.length, b.length),
            i = 0;
        while (i < n && a.charAt(i) === b.charAt(i))
            ++i;
        return a.substring(0, i);

      default:
        // return the common prefix of the first string,
        // and the common prefix of the rest of the strings
        return prefix([ strings[0], prefix(strings.slice(1)) ]);
    }
}

Ответ 8

• не знаю, что знаю

• yes: вместо сравнения подстроки от 0 до длины я вы можете просто проверить i-й символ (вы уже знаете, что символы от 0 до i-1 совпадают).

Ответ 9

Короткий и сладкий вариант, возможно, не самый эффективный:

/// Return length of longest common prefix in an array of strings.
function _commonPrefix($array) {
    if(count($array) < 2) {
        if(count($array) == 0)
            return false; // empty array: undefined prefix
        else
            return strlen($array[0]); // 1 element: trivial case
    }
    $len = max(array_map('strlen',$array)); // initial upper limit: max length of all strings.
    $prevval = reset($array);
    while(($newval = next($array)) !== FALSE) {
        for($j = 0 ; $j < $len ; $j += 1)
            if($newval[$j] != $prevval[$j])
                $len = $j;
        $prevval = $newval;
    }
    return $len;
}

// TEST CASE:
$arr = array('/var/yam/yamyam/','/var/yam/bloorg','/var/yar/sdoo');
print_r($arr);
$plen = _commonprefix($arr);
$pstr = substr($arr[0],0,$plen);
echo "Res: $plen\n";
echo "==> ".$pstr."\n";
echo "dir: ".dirname($pstr.'aaaa')."\n";

Выход тестового примера:

Array
(
    [0] => /var/yam/yamyam/
    [1] => /var/yam/bloorg
    [2] => /var/yar/sdoo
)
Res: 7
==> /var/ya
dir: /var

Ответ 10

@bumperbox

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

  • Ваша петля сравнивается только до символа до последнего символа!
  • Несоответствие может происходить 1 цикл цикла после последнего общего символа.
  • Следовательно, вы должны хотя бы проверить до 1 символа после первого символа последней строки.
  • Следовательно, ваш оператор сравнения должен быть "< = 1" или "< 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));

Ответ 11

Как насчет чего-то подобного? Его можно дополнительно оптимизировать, не проверяя длины строк, если мы можем использовать нулевой завершающий символ (но я предполагаю, что строки python имеют кеширование где-нибудь?)

def find_common_prefix_len(strings):
    """
    Given a list of strings, finds the length common prefix in all of them.
    So
    apple
    applet
    application
    would return 3
    """
    prefix          = 0
    curr_index      = -1
    num_strings     = len(strings)
    string_lengths  = [len(s) for s in strings]
    while True:
        curr_index  += 1
        ch_in_si    = None
        for si in xrange(0, num_strings):
            if curr_index >= string_lengths[si]:
                return prefix
            else:
                if si == 0:
                    ch_in_si = strings[0][curr_index]
                elif strings[si][curr_index] != ch_in_si:
                    return prefix
        prefix += 1

Ответ 12

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

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

Ответ 13

    // 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;

Ответ 14

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

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

Ответ 15

Верхний ответ казался немного длинным, поэтому здесь краткое решение с временем выполнения 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 -

Ответ 16

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

Я использовал это для поиска общего префикса для списка кодов продуктов (т.е. где есть множество 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;
}

Ответ 17

Это дополнение к ответу @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;
}