如何检查一个数组是否是另一个数组的正确排序子集

Question

我有一些类似的字符串数组：

$big = ['html', 'body', 'div', 'table', 'tbody', 'tr', 'td'];
$small = ['body', 'div', 'td'];
$wrong = ['td', 'body', 'div'];

我需要检查是否在$small中找到$wrong和$big。但是我需要顺序相同。因此，我的函数应该为true返回$small，为false返回$wrong。手动执行此操作应该很简单，但是我需要代码快速。因此，理想情况下，如果有内置功能可以实现这一目标，我宁愿使用它。

所以问题主要是是否存在这样的内置对象。如果没有，这是我想出的代码：

/**
 * Returns whether the substack is contained in the stack in the correct order.  
 * 
 * @param string[] $stack           The substack to check
 * @param string[] $subStack        The substack to check 
 * @return bool
 */
function stackInStack(array $stack, array $subStack)
{

    // First let's do a simple array diff to save time on an ordered diff;
    // TODO: Check if this actually improves average performance.
    if (count(array_diff($subStack, $stack)) !== 0) return false;

    $stackSize = count($stack);
    $subStackSize = count($subStack);

    $stackIndex = 0;
    for ($subIndex = 0; $subIndex < $subStackSize; $subIndex++) {

        while (
            $stackIndex < $stackSize &&
            $stack[$stackIndex] !== $subStack[$subIndex]
        ) {
            $stackIndex++;
        }

        if ($stackIndex == $stackSize) {
            if ($subIndex <= $subStackSize - 1) {
                return false;
            } elseif ($subIndex > $subStackSize - 1) {
                throw new Exception('Very Strange Exception: subIndex has outgrown subStacksize');
            }
        } elseif ($stackIndex > $stackSize) {
            throw new Exception('Very Strange Exception: index has outgrown stacksize');
            break;
        } 

    }
    return true;
}

提供的内置程序不存在或速度很慢，任何提高上述代码效率（而不是用c重写）的技巧也将不胜感激。

Answer 1

假设数组不是太大，则可以使用字符串比较。像这样的东西：

<?php

    $big = ['html', 'body', 'div', 'table', 'tbody', 'tr', 'td'];
    //$small = ['body', 'div', 'td']; // This is the original
    $small = ['body', 'div', 'table']; // This is for testing
    $wrong = ['td', 'body', 'div'];

    $bigToken = implode($big, ''); // Output: htmlbodydivtabletbodytrtd
    $smallToken = implode($small, ''); // Output: bodydivtable
    $wrongToken = implode($wrong, ''); // Output: tdbodydiv

    if (stristr($bigToken, $smallToken) !== false) {
        echo("Small is in big!");
    }
    elseif (stristr($bigToken, $wrongToken) !== false) {
        echo("Wrong is in big!");   
    }
    else {
        echo("No match found :)");
    }

?>

它基本上将数组转换为字符串，并检查其中是否包含另一个字符串。在性能方面，这全都取决于实际数组的大小，但这可以确保顺序正确并且更易于维护。

Answer 2

这比您的版本短一点，它使用array_intersect()来计算两个数组中的公共元素，然后将结果与子堆栈进行比较以查看它们是否相同...

$big = ['html', 'body', 'div', 'table', 'tbody', 'tr', 'td'];
$small = ['body', 'div', 'td'];
$wrong = ['td', 'body', 'div'];

function stackInStack(array $stack, array $subStack)
{
    return array_values(array_intersect($stack, $subStack)) == $subStack;
}

var_dump(stackInStack($big, $small));
var_dump(stackInStack($big, $wrong));

仅显示我的意思

print_r(array_intersect($big, $wrong));

给予...

Array
(
    [1] => body
    [2] => div
    [6] => td
)

因此将此与$wrong进行比较，并且顺序不相同。