arrays - 算法问题 - 在列表中查找一组项目

Question

这是我正在尝试做的事情:

我有 2 个列表。

list 1:00F0001,00F0002,00F0003,00F0004,00F0005,00F0006,00F0007,00F0008,00F0009,00F0010

列表 2 : 00F0006,00F0007,00F0008(此列表由第一项($debut)和最后一项($fin)生成)

我想做的是:

如果“List 2”在“List 1”中，就返回 true。

所以我尝试使用 2 for 但我被阻止了 :/

我的代码:

    $id = substr($debut,0,4);
    echo '</br>id : '.$id; /* = 00F0*/

    $Start = substr($debut,4,25);
    $End = substr($fin,4,25);
    $range = $End - $Start +1;

    echo '</br>Range : '.$range; /* = 3 with the example I gave*/

    for ($i = 0;$i < $range;$i++){
        $indice2 = $Start + $i;
        $Num_Serie = str_pad($indice2, 4, '0', STR_PAD_LEFT);
        $Num_Serie_Final[$i] = $id.''.$Num_Serie;
    }
    $ArrayNS = $Num_Serie_Final;
$i_W = 0;
while(($produit = $reponse->fetch())AND($check3 == "false")){

    $ArrayProduit[$i_W] = $produit[1];
    $i_W++;
    }

for ($i2 = 0; $i2 < $i_W; $i2++){
    for ($i3 = 0; $i3 < $range; $i3++){
        if ($ArrayNS[$i2] == $ArrayProduit[$i3]){
          .... ???? .....
        }
    }
}

第一个“for”是构建我的“List 2”。 “while”循环用于生成我的“List 1”

然后我做了一个双“for”循环，但它在这里我锁定了:/

编辑

我为感兴趣的人尝试了一些东西:

    for ($i3 = 0; $i3 < $range; $i3++){
    for ($i2 = 0; $i2 < $i_W; $i2++){
        if ($ArrayNS[$i3] == $ArrayProduit[$i2]){
            for ($indice=0; $indice < $range; $indice++){
                if ($ArrayNS[$indice] == $ArrayProduit[$i2+$indice]){
                    $ok = true;
                    echo '$ArrayNS[$indice] : '.$ArrayNS[$indice].'   ==   $ArrayProduit[$i2+$indice] : '.$ArrayProduit[$i2+$indice].'</br>';
                }
                else {
                    $ok = false;
                    $id_erreur = $ArrayNS[$indice];
                    echo 'Fail with : '.$ArrayNS[$indice].'   !==   '.$ArrayProduit[$i2+$indice].'</br>';
                }
            }
            if ($ok) {
                echo 'Success !!!';
                return ($ok);
            }
            else {
                echo 'Fail !!!';
                return ($id_erreur);
            }
        }
    }
}

可能不是最好的方法，但它有效 ^^

Answer 1

我选择js是为了控制台的可测试性，但是算法在php中是一样的。

这个返回一个索引，但是你只需要检查你的索引是否不同于 -1 来判断它是否已经找到。

想法是遍历大海捞针的每个元素(l1 这里)，如果当前元素匹配我们针的第一个元素(l2)，那么我们开始从当前 haystack 索引 (i) 循环到针索引 (i + j) 的末尾，但是如果这些元素中的任何一个不匹配(在第一次出现)我们跳到 haystack 的下一个值(l1)并重试。如果我们没有失败(failedMatch 标志)，则返回子序列的索引(l2 在 l1 开始位置)。

如果子序列没有出现在 haystack 中，我们按照约定返回 -1。

这是从左到右的方法，因此它只会匹配子序列的第一次出现，如果它出现不止一次，你就不知道了。

var l1 = [1,2,3,3,4,5,6],
    l2 = [3,4,5];

function subsequenceIndex(l1 /* haystack */, l2 /* needle */) {
    var startIndex = -1,
        failedMatch;

    for (var i = 0; i < l1.length; i++) {
        failedMatch = false;
        if (l1[i] === l2[0]) {

            for (var j = 1; j < l2.length; j++) {

                // check first that l1[i + j] is set
                if (l1[i + j] !== undefined && l2[j] !== l1[i + j]) {
                    failedMatch = true;
                    break;
                }
            }

            if (!failedMatch) {
                startIndex = i;
            }

        }
        if (startIndex !== -1) {
            return startIndex;
        }
     }

    return startIndex;
}