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

Я внедрил алгоритм @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 */ 

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

 $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; } } 

Обновление Вот еще одно решение, итеративное сравнение каждого 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 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ознакомьтесь с WikiPedia для описания нотации Big Theta.

Вот изящная, рекурсивная реализация в 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)) ]); } } 

1. не то, что я знаю из

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

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

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

@bumperbox

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

   • Ваша петля сравнивается только до одного символа перед последним символом!
   • Несоответствие может происходить 1 цикл цикла после последнего общего символа.
   • Следовательно, вы должны хотя бы проверить до 1 символа после последнего символа первой строки.
   • Следовательно, ваш оператор сравнения должен быть «<= 1» или «<2».

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)); самая 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)); самая 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)); самая 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)); самая 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)); 

Как насчет чего-то подобного? Его можно дополнительно оптимизировать, не проверяя длины строк, если мы можем использовать нуль-завершающий символ (но я предполагаю, что строки 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 

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

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

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

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

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

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

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

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

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