Тетрирование массива

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

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

Загрузите их в структуру данных trie. Начиная с родительского узла, посмотрите, у кого есть число детей, отличное от одного. Как только вы найдете этот магический узел, просто демонтируйте структуру родительского узла и укажите текущий узел как root.

 $common = PHP_INT_MAX; foreach ($a as $item) { $common = min($common, str_common($a[0], $item, $common)); } $result = array(); foreach ($a as $item) { $result[] = substr($item, $common); } print_r($result); function str_common($a, $b, $max) { $pos = 0; $last_slash = 0; $len = min(strlen($a), strlen($b), $max + 1); while ($pos < $len) { if ($a{$pos} != $b{$pos}) return $last_slash; if ($a{$pos} == '/') $last_slash = $pos; $pos++; } return $last_slash; } 

Ну, учитывая, что вы можете использовать XOR в этой ситуации, чтобы найти общие части строки. Каждый раз, когда вы xor два байта одинаковы, вы получаете нулевой байт в качестве вывода. Поэтому мы можем использовать это в наших интересах:

 $first = $array[0]; $length = strlen($first); $count = count($array); for ($i = 1; $i < $count; $i++) { $length = min($length, strspn($array[$i] ^ $first, chr(0))); } 

После этого одиночного цикла переменная $length будет равна самой длинной общей базовой части между массивом строк. Затем мы можем извлечь общую часть из первого элемента:

 $common = substr($array[0], 0, $length); 

И вот он у вас есть. Как функция:

 function commonPrefix(array $strings) { $first = $strings[0]; $length = strlen($first); $count = count($strings); for ($i = 1; $i < $count; $i++) { $length = min($length, strspn($strings[$i] ^ $first, chr(0))); } return substr($first, 0, $length); } 

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

Теперь, если вы хотите только полные пути, нам нужно усечь до последнего / символа. Так:

 $prefix = preg_replace('#/[^/]*$', '', commonPrefix($paths)); 

Теперь он может чрезмерно разрезать две строки, такие как /foo/bar и /foo/bar/baz будет отрезаться до /foo . Но, не добавляя еще один раунд итерации, чтобы определить, является ли следующий символ либо / или окончанием строки, я не вижу пути вокруг этого …

Наивный подход заключался бы в том, чтобы взорвать пути в / и последовательном сравнении каждого элемента в массивах. Таким образом, например, первый элемент будет пустым во всех массивах, поэтому он будет удален, следующий элемент будет www , он будет одинаковым во всех массивах, поэтому он будет удален и т. Д.

Что-то вроде ( непроверенной )

 $exploded_paths = array(); foreach($paths as $path) { $exploded_paths[] = explode('/', $path); } $equal = true; $ref = &$exploded_paths[0]; // compare against the first path for simplicity while($equal) { foreach($exploded_paths as $path_parts) { if($path_parts[0] !== $ref[0]) { $equal = false; break; } } if($equal) { foreach($exploded_paths as &$path_parts) { array_shift($path_parts); // remove the first element } } } 

Впоследствии вам просто нужно снова размотать элементы в $exploded_paths :

 function impl($arr) { return '/' . implode('/', $arr); } $paths = array_map('impl', $exploded_paths); 

Что дает мне:

 Array ( [0] => /lib/abcdedd [1] => /conf/xyz [2] => /conf/abc/def [3] => /htdocs/xyz [4] => /conf/xyz ) 

Это может плохо масштабироваться;)

Хорошо, я не уверен, что это пуленепробиваемый, но я думаю, что это работает:

 echo array_reduce($array, function($reducedValue, $arrayValue) { if($reducedValue === NULL) return $arrayValue; for($i = 0; $i < strlen($reducedValue); $i++) { if(!isset($arrayValue[$i]) || $arrayValue[$i] !== $reducedValue[$i]) { return substr($reducedValue, 0, $i); } } return $reducedValue; }); 

Это займет первое значение в массиве в качестве ссылочной строки. Затем он будет перебирать ссылочную строку и сравнивать каждый символ с символом второй строки в той же позиции. Если символ не соответствует, эталонная строка будет сокращена до позиции символа, а следующая строка будет сравниваться. Затем функция вернет самую короткую совпадающую строку.

Производительность зависит от заданных строк. Чем раньше ссылочная строка становится короче, тем быстрее заканчивается код. Я действительно не знаю, как это сделать в формуле.

Я обнаружил, что подход Artefacto для сортировки строк увеличивает производительность. Добавление

 asort($array); $array = array(array_shift($array), array_pop($array)); 

до того, как array_reduce значительно увеличит производительность.

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

 substr($result, 0, strrpos($result, '/')); 

на результат. И затем вы можете использовать результат для удаления значений

 print_r(array_map(function($v) use ($path){ return str_replace($path, '', $v); }, $array)); 

который должен дать:

 [0] => /lib/abcdedd [1] => /conf/xyz/ [2] => /conf/abc/def [3] => /htdocs/xyz [4] => /lib2/abcdedd 

Обратная связь приветствуется.

Вы можете удалить префикс самым быстрым способом, прочитав каждый символ только один раз:

 function findLongestWord($lines, $delim = "/") { $max = 0; $len = strlen($lines[0]); // read first string once for($i = 0; $i < $len; $i++) { for($n = 1; $n < count($lines); $n++) { if($lines[0][$i] != $lines[$n][$i]) { // we've found a difference between current token // stop search: return $max; } } if($lines[0][$i] == $delim) { // we've found a complete token: $max = $i + 1; } } return $max; } $max = findLongestWord($lines); // cut prefix of len "max" for($n = 0; $n < count($lines); $n++) { $lines[$n] = substr(lines[$n], $max, $len); } 

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

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

 sort($a); $a = array_map(function ($el) { return explode("/", $el); }, $a); $first = reset($a); $last = end($a); for ($eqdepth = 0; $first[$eqdepth] === $last[$eqdepth]; $eqdepth++) {} array_walk($a, function (&$el) use ($eqdepth) { for ($i = 0; $i < $eqdepth; $i++) { array_shift($el); } }); $res = array_map(function ($el) { return implode("/", $el); }, $a); 

 $values = array('/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function splitArrayValues($r) { return explode('/',$r); } function stripCommon($values) { $testValues = array_map('splitArrayValues',$values); $i = 0; foreach($testValues[0] as $key => $value) { foreach($testValues as $arraySetValues) { if ($arraySetValues[$key] != $value) break 2; } $i++; } $returnArray = array(); foreach($testValues as $value) { $returnArray[] = implode('/',array_slice($value,$i)); } return $returnArray; } $newValues = stripCommon($values); echo '<pre>'; var_dump($newValues); echo '</pre>'; 

EDIT Вариант моего исходного метода с использованием array_walk для восстановления массива

 $values = array('/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function splitArrayValues($r) { return explode('/',$r); } function rejoinArrayValues(&$r,$d,$i) { $r = implode('/',array_slice($r,$i)); } function stripCommon($values) { $testValues = array_map('splitArrayValues',$values); $i = 0; foreach($testValues[0] as $key => $value) { foreach($testValues as $arraySetValues) { if ($arraySetValues[$key] != $value) break 2; } $i++; } array_walk($testValues, 'rejoinArrayValues', $i); return $testValues; } $newValues = stripCommon($values); echo '<pre>'; var_dump($newValues); echo '</pre>'; 

РЕДАКТИРОВАТЬ

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

Я бы explode значения на основе /, а затем использовал array_intersect_assoc для обнаружения общих элементов и обеспечения того, что они имеют правильный соответствующий индекс в массиве. Полученный массив может быть рекомбинирован для получения общего пути.

 function getCommonPath($pathArray) { $pathElements = array(); foreach($pathArray as $path) { $pathElements[] = explode("/",$path); } $commonPath = $pathElements[0]; for($i=1;$i<count($pathElements);$i++) { $commonPath = array_intersect_assoc($commonPath,$pathElements[$i]); } if(is_array($commonPath) return implode("/",$commonPath); else return null; } function removeCommonPath($pathArray) { $commonPath = getCommonPath($pathArray()); for($i=0;$i<count($pathArray);$i++) { $pathArray[$i] = substr($pathArray[$i],str_len($commonPath)); } return $pathArray; } 

Это непроверено, но идея состоит в том, что массив $commonPath только когда-либо содержит элементы пути, которые содержались во всех массивах путей, которые были сопоставлены с ним. Когда цикл завершен, мы просто рекомбинируем его с /, чтобы получить истинный $commonPath

Обновление Как отметил Феликс Клинг, array_intersect не будет рассматривать пути, которые имеют общие элементы, но в разных порядках … Чтобы решить эту проблему, я использовал array_intersect_assoc вместо array_intersect

Обновление Добавлен код, чтобы удалить общий путь (или тетрис!) Из массива.

Проблема может быть упрощена, если только просмотреть из угла сравнения строк. Это, вероятно, быстрее, чем разбиение массива:

 $longest = $tetris[0]; # or array_pop() foreach ($tetris as $cmp) { while (strncmp($longest+"/", $cmp, strlen($longest)+1) !== 0) { $longest = substr($longest, 0, strrpos($longest, "/")); } } 

Возможно, портирование алгоритма работы os.path.commonprefix(m) будет работать?

 def commonprefix(m): "Given a list of pathnames, returns the longest common leading component" if not m: return '' s1 = min(m) s2 = max(m) n = min(len(s1), len(s2)) for i in xrange(n): if s1[i] != s2[i]: return s1[:i] return s1[:n] 

То есть, ну … что-то вроде

 function commonprefix($m) { if(!$m) return ""; $s1 = min($m); $s2 = max($m); $n = min(strlen($s1), strlen($s2)); for($i=0;$i<$n;$i++) if($s1[$i] != $s2[$i]) return substr($s1, 0, $i); return substr($s1, 0, $n); } 

После этого вы можете просто подстроить каждый элемент исходного списка длиной общего префикса в качестве начального смещения.

Я брошу свою шляпу на ринг …

 function longestCommonPrefix($a, $b) { $i = 0; $end = min(strlen($a), strlen($b)); while ($i < $end && $a[$i] == $b[$i]) $i++; return substr($a, 0, $i); } function longestCommonPrefixFromArray(array $strings) { $count = count($strings); if (!$count) return ''; $prefix = reset($strings); for ($i = 1; $i < $count; $i++) $prefix = longestCommonPrefix($prefix, $strings[$i]); return $prefix; } function stripPrefix(&$string, $foo, $length) { $string = substr($string, $length); } 

Применение:

 $paths = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd', ); $longComPref = longestCommonPrefixFromArray($paths); array_walk($paths, 'stripPrefix', strlen($longComPref)); print_r($paths); 

Ну, здесь уже есть некоторые решения, но просто потому, что это было весело:

 $values = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function findCommon($values){ $common = false; foreach($values as &$p){ $p = explode('/', $p); if(!$common){ $common = $p; } else { $common = array_intersect_assoc($common, $p); } } return $common; } function removeCommon($values, $common){ foreach($values as &$p){ $p = explode('/', $p); $p = array_diff_assoc($p, $common); $p = implode('/', $p); } return $values; } echo '<pre>'; print_r(removeCommon($values, findCommon($values))); echo '</pre>'; 

Вывод:

 Array ( [0] => lib/abcdedd [1] => conf/xyz [2] => conf/abc/def [3] => htdocs/xyz [4] => lib2/abcdedd ) 

 $arrMain = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); function explodePath( $strPath ){ return explode("/", $strPath); } function removePath( $strPath) { global $strCommon; return str_replace( $strCommon, '', $strPath ); } $arrExplodedPaths = array_map( 'explodePath', $arrMain ) ; //Check for common and skip first 1 $strCommon = ''; for( $i=1; $i< count( $arrExplodedPaths[0] ); $i++) { for( $j = 0; $j < count( $arrExplodedPaths); $j++ ) { if( $arrExplodedPaths[0][ $i ] !== $arrExplodedPaths[ $j ][ $i ] ) { break 2; } } $strCommon .= '/'.$arrExplodedPaths[0][$i]; } print_r( array_map( 'removePath', $arrMain ) ); 

Это отлично работает … похоже на mark baker, но использует str_replace

Наверное, слишком наивно и noobish, но он работает. Я использовал этот алгоритм :

 <?php function strlcs($str1, $str2){ $str1Len = strlen($str1); $str2Len = strlen($str2); $ret = array(); if($str1Len == 0 || $str2Len == 0) return $ret; //no similarities $CSL = array(); //Common Sequence Length array $intLargestSize = 0; //initialize the CSL array to assume there are no similarities for($i=0; $i<$str1Len; $i++){ $CSL[$i] = array(); for($j=0; $j<$str2Len; $j++){ $CSL[$i][$j] = 0; } } for($i=0; $i<$str1Len; $i++){ for($j=0; $j<$str2Len; $j++){ //check every combination of characters if( $str1[$i] == $str2[$j] ){ //these are the same in both strings if($i == 0 || $j == 0) //it's the first character, so it's clearly only 1 character long $CSL[$i][$j] = 1; else //it's one character longer than the string from the previous character $CSL[$i][$j] = $CSL[$i-1][$j-1] + 1; if( $CSL[$i][$j] > $intLargestSize ){ //remember this as the largest $intLargestSize = $CSL[$i][$j]; //wipe any previous results $ret = array(); //and then fall through to remember this new value } if( $CSL[$i][$j] == $intLargestSize ) //remember the largest string(s) $ret[] = substr($str1, $i-$intLargestSize+1, $intLargestSize); } //else, $CSL should be set to 0, which it was already initialized to } } //return the list of matches return $ret; } $arr = array( '/www/htdocs/1/sites/lib/abcdedd', '/www/htdocs/1/sites/conf/xyz', '/www/htdocs/1/sites/conf/abc/def', '/www/htdocs/1/sites/htdocs/xyz', '/www/htdocs/1/sites/lib2/abcdedd' ); // find the common substring $longestCommonSubstring = strlcs( $arr[0], $arr[1] ); // remvoe the common substring foreach ($arr as $k => $v) { $arr[$k] = str_replace($longestCommonSubstring[0], '', $v); } var_dump($arr); 

Вывод:

 array(5) { [0]=> string(11) "lib/abcdedd" [1]=> string(8) "conf/xyz" [2]=> string(12) "conf/abc/def" [3]=> string(10) "htdocs/xyz" [4]=> string(12) "lib2/abcdedd" } 

🙂