如果一个阵列包含在另一确定 [英] Determining if one array is contained in another

问题描述

我如何判断一个数组中的另一个数组包含（元素通过元素和顺序）？我已经写了下面的程序在2010年MSVS，但也不太清楚如何完成布尔函数，确定如果一个阵列出现在另一个

 无效isContained（INT AR1 []，INT AR2 []）;
INT主（INT ARGC，字符** argv的）
{
    ifstream的FIN1（one.txt）;
    ifstream的FIN2（two.txt来办到）;    INT I，J，值1，值;
    INT ARR1 [10];
    INT ARR2 [10];    对于（i = 0;＆FIN1 GT;＆GT;值1;我++）
    {
        ARR1 [I] =值;
    }    为（J = 0;＆FIN2 GT;＆GT;值2; J ++）
    {
        ARR2 [J] =值;
    }    isContained（ARR1，ARR2）;    系统（暂停）;
}
无效isContained（INT AR1 []，INT AR2 []）
{
    ???
}
 

解决方案

简单。比方说，你要检查 AR2 包含在 AR1 。

一个例子：

 的Ar 1：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

您必须经过的Ar 1 ，找到 AR2 的第一个元素相匹配，然后从那里上的元素，尝试看看是否所有元素相匹配。如果没有，你继续的Ar 1 找到 AR2

的第一个元素匹配的另一个元素

所以基本上code会是这个样子：

 如果（Ar2_len == 0）
    返回true;
为（unsigned int类型I = 0; I＆LT; Ar1​​_len-（Ar2_len-1）+ I）
    如果（的Ar 1 [I] == AR2 [0]）
    {
        布尔匹配= TRUE;
        对（无符号整数J = 1; J＆LT; Ar2_len ++ j）条
            如果（的Ar 1 [I + J] == AR2 [J]。）
            {
                比赛= FALSE;
                打破;
            }
        如果（匹配）
            返回true;
    }
 

注意 I 进入 Ar1_len-（Ar2_len-1），因为如果你到底太远的Ar 1 （其中有不到 Ar2_len 元素是左），这显然是不可能找到 AR2 。

其次值得注意的是，这不是最有效的方法。最有效的方法包括从 AR2 构建DFA，并使用的Ar 1 作为输入和跟踪它。如果达到最后的状态你返回true 。这可能是一个有点复杂了，你知道的，但如果你有兴趣，你可以查找算法字符串匹配。

最后说明的是，这里提供的code是不是意味着复制粘贴。它可能缺乏足够的错误检查和完全是在这里给你的想法。

How do I determine if one array is contained (element by element and in order) in another array? I have written the program below in MSVS 2010 but not too sure how to complete the boolean function that determines if one array appears in the other one

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[] )
{
    ???
}

解决方案

Simple. Let's say you want to check if ar2 is contained in ar1.

An example:

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

Let's also assume you have the lengths of the arrays in Ar1_len and Ar2_len

You have to go through Ar1, find an element that matches the first element of Ar2 then from there on, try to see if all elements match. If not, you continue on Ar1 to find another element that matches the first element of Ar2

So basically the code would look something like this:

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

Note that i goes to Ar1_len-(Ar2_len-1) because if you are too far in the end of Ar1 (where there are less than Ar2_len elements are left), it's obviously impossible to find Ar2.

Second note is that this is not the most efficient method. The most efficient method involves building a DFA from Ar2 and using Ar1 as its input and trace it. If it reaches final state you return true. This is probably a bit complicated for you know, but if you are interested, you could look up algorithms in string matching.

Final note is that, the code provided here is not meant for copy-paste. It may lack sufficient error checking and is solely here to give you the idea.

这篇关于如果一个阵列包含在另一确定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！