俄罗斯方块数组
考虑下面的数组：
/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 在这种情况下，检测公共基path的最短和最优雅的方式是什么？
/www/htdocs/1/sites/
并从数组中的所有元素中删除它？
lib/abcdedd conf/xyz conf/abc/def htdocs/xyz lib2/abcdedd
编写一个将两个string作为input的函数longest_common_prefix 。 然后以任何顺序将其应用到string，以将它们减less到它们的通用前缀。 由于它是联想和交换的顺序并不重要的结果。
这与其他二进制操作（例如加法或最大公约数）相同。
将它们加载到trie数据结构中。 从父节点开始，查看哪个孩子的数量多于一个。 一旦find魔术节点，只需拆除父节点结构并以当前节点为根。
$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来查找string的公共部分。 任何时候你不相同的两个字节，你会得到一个空字节作为输出。 所以我们可以利用这个优势：
$first = $array[0]; $length = strlen($first); $count = count($array); for ($i = 1; $i < $count; $i++) { $length = min($length, strspn($array[$i] ^ $first, chr(0))); }
在单循环之后， $lengthvariables将等于string数组之间最长的公共基本部分。 然后，我们可以从第一个元素中提取公共部分：
$common = substr($array[0], 0, $length);
在那里，你有它。 作为一个function：
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); }
请注意，它使用了多次迭代，但这些迭代是在库中完成的，因此在解释型语言中，这将具有巨大的效率增益。
现在，如果你只想要完整的path，我们需要截断到最后的/字符。 所以：
$prefix = preg_replace('#/[^/]*$', '', commonPrefix($paths));
现在，它可能会过度剪切两个string，例如/foo/bar ， /foo/bar/baz将被剪切到/foo 。 但是，为了确定下一个字符是/ 还是string结束，再加上一个循环，我就看不到一个方法了。
一个幼稚的方法是在/分解path并连续比较数组中的每个元素。 因此，例如，所有数组中的第一个元素都是空的，所以它将被删除，下一个元素将是www ，它在所有数组中都是一样的，所以它被删除等等。
就像是 （ 未经testing ）
$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; });
这将把数组中的第一个值作为参考string。 然后它将遍历引用string，并将每个字符与第二个string的字符在同一位置进行比较。 如果char不匹配，则引用string将被缩短到char的位置，并比较下一个string。 该函数将返回最短的匹配string。
性能取决于给定的string。 参考string越早，代码越快。 我真的不知道如何把它放在一个公式中。
我发现Artefacto对stringsorting的方法提高了性能。 添加
asort($array); $array = array(array_shift($array), array_pop($array));
在array_reduce之前会显着提高性能。
另外请注意，这将返回最长的匹配初始子string ，这是更通用的，但不会给你共同的path 。 你必须跑步
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); }
这有利于不具有线性时间复杂度; 然而，在大多数情况下，这种做法绝对不会花费更多的时间。
基本上，巧妙的部分（至less我不能find它的错误）在这里是sorting后，你只需要比较第一个path和最后一个。
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>';
编辑使用array_walk重build数组我的原始方法的变体
$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>';
编辑
最有效和最优雅的答案可能涉及从每个提供的答案中获取function和方法
我会explode基于/的值，然后使用array_intersect_assoc来检测公共元素，并确保他们有正确的相应的索引在数组中。 由此产生的数组可以重新组合产生共同的path。
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; }
这是未经testing的，但是，这个想法是， $commonPath数组只包含已经包含在所有path数组中的path的元素，这些元素已经与它进行了比较。 当循环完成时，我们简单地使用/来重新获得真正的$commonPath
更新正如Felix Kling所指出的， array_intersect不会考虑具有相同元素但具有不同顺序的path…为了解决这个问题，我使用了array_intersect_assoc而不是array_intersect
更新添加代码以从数组中删除公共path（或俄罗斯方块！）。
如果从string比较angular度来看问题可以简化。 这可能比数组拆分更快：
$longest = $tetris[0]; # or array_pop() foreach ($tetris as $cmp) { while (strncmp($longest+"/", $cmp, strlen($longest)+1) !== 0) { $longest = substr($longest, 0, strrpos($longest, "/")); } }
也许移植Python的os.path.commonprefix(m)使用的algorithm将工作？
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);
那么，这里已经有了一些解决scheme，只是因为它很有趣：
$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 ) );
这工作正常…类似标记面包师，但使用str_replace
可能太天真，不太好，但它的作品。 我已经使用这个algorithm ：
<?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" }
🙂
