[php] 배열 테트리스

Program / 글쓴이

다음 배열을 고려하십시오.

/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

답변

longest_common_prefix두 개의 문자열을 입력으로 받는 함수 를 작성하십시오 . 그런 다음 임의의 순서로 문자열에 적용하여 공통 접두사로 줄이십시오. 연관적이고 교환 적이므로 순서는 결과에 중요하지 않습니다.

이것은 덧셈이나 최대 공약수와 같은 다른 이진 연산과 동일합니다.

답변

트라이 데이터 구조에로드합니다. 부모 노드에서 시작하여 자식이 1보다 큰지 확인하십시오. 매직 노드를 찾으면 부모 노드 구조를 해체하고 현재 노드를 루트로 만드십시오.

답변

$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이 상황에서 문자열의 공통 부분을 찾기 위해 사용할 수 있다는 점을 고려 하십시오. 동일한 2 바이트를 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. 다음 문자 중 하나입니다하지만 다른 반복 라운드를 추가하는 짧은 결정 / 또는 최종의 문자열, 내가 그 주위에 방법을 볼 수 없습니다 …

답변

순진한 접근 방식은 경로를 폭파 /하고 배열의 모든 요소를 ​​연속적으로 비교하는 것입니다. 예를 들어 첫 번째 요소는 모든 배열에서 비어 있으므로 제거되고 다음 요소는 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);
}