确定一个数组是否包含在另一个数组中

Question

如何确定一个数组是否以相同的顺序（逐个元素）包含在另一个数组中？我已经在MSVS 2010中编写了下面的程序，但不太确定如何完成判断一个数组是否出现在另一个数组中的布尔函数。

void isContained( int ar1[], int ar2[] );


int main( int argc, char** argv )
{
    ifstream fin1( "one.txt" );
    ifstream fin2( "two.txt" );

    int i, j, value1, value2;
    int arr1[ 10 ];
    int arr2[ 10 ];

    for ( i = 0 ; fin1 >> value1 ; i++ )
    {
        arr1[ i ] = value1;
    }

    for ( j = 0 ; fin2 >> value2 ; j++ )
    {
        arr2[ j ] = value2;
    }

    isContained( arr1, arr2 );

    system( "PAUSE" );
}


void isContained( int ar1[], int ar2[] )
{
    ???
}

- user285372

---

你可以使用 <algorithm> 中的 std::search 函数。标准库中有很多有用的函数，你可能需要熟悉文档。 - Blastfurnace

Answer 1

你需要的是一种字符串搜索算法（不过在你的情况下，“字符”是数组中的整数元素）。

有许多这样的算法，详见Wikipedia。

就你目前的代码而言：

1. 你可能想确保在两个for循环中不要超出数组的末尾。 2. 你需要将两个数组的大小传递给isContained（它的返回类型可能不应该是void）。

- NPE

Answer 2

简单来说，假设你想要检查ar2是否包含在ar1中。

举个例子：

Ar1: 1 2 3 4 5 6 7 8 9 10 5 2 8 2 4 2 4 6 2 9 1
Ar2: 2 4 6 2

假设您也有数组长度Ar1_len和Ar2_len

您需要遍历Ar1，查找与Ar2的第一个元素相匹配的元素，然后从那里开始，尝试查看是否所有元素都匹配。如果不匹配，则继续在Ar1上寻找另一个与Ar2的第一个元素匹配的元素

因此，基本上代码看起来像这样:

if (Ar2_len == 0)
    return true;
for (unsigned int i = 0; i < Ar1_len-(Ar2_len-1); ++i)
    if (Ar1[i] == Ar2[0])
    {
        bool matches = true;
        for (unsigned int j = 1; j < Ar2_len; ++j)
            if (Ar1[i+j] != Ar2[j])
            {
                matches = false;
                break;
            }
        if (matches)
            return true;
    }

请注意，i 的值为 Ar1_len-(Ar2_len-1)，因为如果你在 Ar1 的末尾（剩余元素少于 Ar2_len 个），显然无法找到 Ar2。

第二点需要注意的是，这不是最有效的方法。最有效的方法是从 Ar2 构建一个 DFA，并将 Ar1 作为其输入并跟踪它。如果它达到了最终状态，则返回 true。这可能有点复杂，但如果您感兴趣，可以查找字符串匹配算法。

最后一点需要注意的是，此处提供的代码不适用于复制粘贴。它可能缺乏足够的错误检查，仅在此处提供给您想法。

- Shahbaz

---

请注意，条件Ar1 [i] == Ar2 [0] 是循环条件Ar1 [i + j] == Ar2 [j]的j==0情况，并且可以轻松合并到其中。（不要重复自己原则/单一责任原则，您知道的吧？） - xtofl

...而且循环和它的相等性检查等同于std::mismatch。 - xtofl

Answer 3

您可以找到在包含数组中使mismatch返回所包含数组结尾的位置:

using namespace std;

template<typename OutIt, typename SeqIt>
OutIt find_sequence( OutIt outer_begin   , OutIt outer_end, 
                     SeqIt sequence_begin, SeqIt sequence_end ){
   assert( 
        distance(outer_begin,outer_end) >= distance(sequence_begin,sequence_end);

   // limit the possible iterator positions:
   OutIt outer_limit = outer_begin;
   advance( outer_limit, distance(sequence_begin, sequence_end) );

   for( OutIt outer_it = outer_begin; outer_it != outer_limit; ++outer_it ) 
   {
     if( mismatch( sequence_begin, sequence_end, outer_it ).first==sequence_end) 
     {
          return outer_it;
     }
   }
   // none found...
   return outer_end;
}

像这样使用：

 int values[]  = { 1,2,3,4,5, 6 };

 int pattern[] = { 3,4,5 };

 int* pFound = find_sequence( values, end(values), pattern, end(pattern) );
 bool bFound = pFound != std::end(values);

- xtofl

Answer 4

你可以使用 <algorithm> 中的 std::search 模板来在另一个序列中搜索子序列。注意：我修改了你的函数签名以传递数组大小。

bool isContained(int ar1[], int size1, int ar2[], int size2)
{
    return std::search(ar1, ar1 + size1, ar2, ar2 + size2) != (ar1 + size1);
}

- Blastfurnace

Answer 5

这与在字符串中搜索子字符串相同。我们在那里比较字符，在这里我们将比较数字或数组元素。

KMP1算法是用于此类问题的。

- bitbyter

---

为什么会有负评呢？那个人能告诉我哪里错了吗？ - bitbyter

Answer 6

使用您提供的原型是不可能的。

当传递给函数时，数组会衰减为指针，因此函数无法确定数组中有多少个元素。

- Šimon Tóth

---

如果数组以特殊值（0？）结尾，则是这样的。 - Simon

@Simon 当你从用户读取数据时，这有点不可能。 - Šimon Tóth