Checking if Table A contains Table B

Question

I am a beginner in programming, especially in Scilab.

I need your help to write this short algorithm:

We have 2, sorted, non-decreasing tables A=[1,2,2,2,3,4,4,4,5,8,10] and B=[2,2,3,4,4,4]. Table A will always be bigger then Table B. I need your help constructing The algorytm for checking whether the table B is contained entirely in the table A (without violating the order of the elements of the B array).

So for tables A=[1,2,2,2,3,4,4,4,5,8,10] and B=[2,2,3,4,4,4] the condition is met.

i have this for now

function sprawdz (A,B, n, m)
A=[2 3 0 5 1 1 2]
B=[3 0 5 1]
n=length(A)
m=length(B)
i=1
j=1
while (i<n && j<m)
    if A(i)==B(j) then
        i=i+1
        j=j+1
        if (j==m) then
             return %t
             break
        end
    else 
        i=i+1
        j=1
    end
end
return %f
if sprawdz (A,B, n, m) == %t then
    disp("spoko")
else 
    disp("nie")
end

endfunction

Answer 1

In Scilab language, we can simply write vectorfind(A,B) that returns all positions in A where B is met and starts:

--> A = [1,2,2,2,3,4,4,4,5,8,10], B = [2,2,3,4,4,4]
 A  = 
   1.   2.   2.   2.   3.   4.   4.   4.   5.   8.   10.
 B  = 
   2.   2.   3.   4.   4.   4.
--> vectorfind(A, B)
 ans  =
   3.

vectorfind() does not require from A or/and B to be sorted. In addition, it can work with some wildcards. A is an array with any number of dimensions: 1D (vector), 2D (matrix), 3D, .. ND

If you just need a boolean answer:

vectorfind(A,B)<>[]

For illustrated examples or more information: https://help.scilab.org/docs/6.1.1/en_US/vectorfind.html

Answer 2

below code checks if an array contains all elements in another array:

public static boolean linearIn(Integer[] outer, Integer[] inner) {

   return Arrays.asList(outer).containsAll(Arrays.asList(inner));
}

In your case there will be your two array

Another approch if you want to check contiguous subsequence Simple Approach:

A simple approach is to run two nested loops and generate all subarrays of the array A[] and use one more loop to check if any of the subarray of A[] is equal to the array B[].

• Efficient Approach :

An efficient approach is to use two pointers to traverse both the array simultaneously. Keep the pointer of array B[] still and if any element of A[] matches with the first element of B[] then increase the pointer of both the array else set the pointer of A to the next element of the previous starting point and reset the pointer of B to 0. If all the elements of B are matched then print YES otherwise print NO.

Below is the implementation of the above approach:

class SubTable {

    // Function to check if an array is subarray of another array
    static boolean isSubArray(int A[], int B[],
                                   int n, int m)
    {
        // Two pointers to traverse the arrays
        int i = 0, j = 0;
     
        // Traverse both arrays simultaneously
        while (i < n && j < m)
        {
     
            // If element matches
            // increment both pointers
            if (A[i] == B[j])
            {
     
                i++;
                j++;
     
                // If array B is completely
                // traversed
                if (j == m)
                    return true;
            }
             
            // If not,
            // increment i and reset j
            else
            {
                i = i - j + 1;
                j = 0;
            }
        }
        return false;
    }
     
    public static void main(String arr[])
    {
        int A[] = { 2, 3, 0, 5, 1, 1, 2 };
        int n = A.length;
        int B[] = { 3, 0, 5, 1 };
        int m = B.length;
     
        if (isSubArray(A, B, n, m))
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}