俄罗斯方块阵列

Question

考虑以下数组:

/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

什么是检测公共基本路径的最短和最优雅的方法- 在这种情况下

/www/htdocs/1/sites/

并从数组中的所有元素中删除它？

lib/abcdedd
conf/xyz
conf/abc/def
htdocs/xyz
lib2/abcdedd

Answer 1

编写一个longest_common_prefix以两个字符串作为输入的函数.然后以任何顺序将它应用于字符串,以将它们减少为它们的公共前缀.由于它是关联的和可交换的,因此顺序对结果无关紧要.

这与其他二元运算相同,例如加法或最大公约数.

Answer 2

将它们加载到trie数据结构中.从父节点开始,查看哪个子节点数大于1.一旦找到该魔术节点,只需拆除父节点结构并将当前节点作为根节点.

Answer 3

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

Answer 4

好吧,考虑到你可以XOR在这种情况下使用来找到字符串的公共部分.每当xor两个字节相同时,就会得到一个nullbyte作为输出.所以我们可以利用它来发挥我们的优势:

$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.但是,如果没有添加另一个迭代循环以确定下一个字符是字符串/ 还是字符串结尾,我无法看到解决方法......