Comprobar si un Array es Subarray de otro Array

Dadas dos arrays A[] y B[] que consisten en  nortemetronúmeros enteros. La tarea es comprobar si el arreglo B[] es un subarreglo del arreglo A[] o no.
Ejemplos
 

Entrada : A[] = {2, 3, 0, 5, 1, 1, 2}, B[] = {3, 0, 5, 1} 
Salida : Sí
Entrada : A[] = {1, 2, 3 , 4, 5}, B[] = {2, 5, 6} 
Salida : No 
 

Fuente : Visa Interview Experience
Enfoque simple : un enfoque simple es ejecutar dos bucles anidados y generar todos los subarreglos de la array A[] y usar un bucle más para verificar si alguno de los subarreglos de A[] es igual a la array B[ ].
Enfoque eficiente : un enfoque eficiente es usar dos punteros para atravesar la array simultáneamente. Mantenga el puntero de la array B[] inmóvil y si algún elemento de A[] coincide con el primer elemento de B[], aumente el puntero de la array; de lo contrario, establezca el puntero de A en el siguiente elemento del punto de inicio anterior y restablezca el puntero de B a 0. Si todos los elementos de B coinciden, imprima SÍ; de lo contrario, imprima NO.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to check if an array is
// subarray of another array
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to check if an array is
// subarray of another array
bool 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;
}
  
// Driver Code
int main()
{
    int A[] = { 2, 3, 0, 5, 1, 1, 2 };
    int n = sizeof(A) / sizeof(int);
    int B[] = { 3, 0, 5, 1 };
    int m = sizeof(B) / sizeof(int);
  
    if (isSubArray(A, B, n, m))
        cout << "YES\n";
    else
        cout << "NO\n";
  
    return 0;
}

Java

// Java program to check if an array is
// subarray of another array
class gfg 
{
      
    // 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;
    }
      
    // Driver Code
    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");
    }
}
  
// This code is contributed by gp6

Python3

# Python3 program to check if an array is 
# subarray of another array 
  
# Function to check if an array is
# subarray of another array
def isSubArray(A, B, n, m):
      
    # Two pointers to traverse the arrays
    i = 0; j = 0;
  
    # Traverse both arrays simultaneously
    while (i < n and j < m):
  
        # If element matches
        # increment both pointers
        if (A[i] == B[j]):
  
            i += 1;
            j += 1;
  
            # 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;
  
# Driver Code
if __name__ == '__main__':
    A = [ 2, 3, 0, 5, 1, 1, 2 ];
    n = len(A);
    B = [ 3, 0, 5, 1 ];
    m = len(B);
  
    if (isSubArray(A, B, n, m)):
        print("YES");
    else:
        print("NO");
  
# This code is contributed by Rajput-Ji

C#

// C# program to check if an array is
// subarray of another array
using System;
  
public class GFG 
{
       
    // Function to check if an array is
    // subarray of another array
    static bool 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;
    }
       
    // Driver Code
    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))
            Console.WriteLine("YES");
        else
            Console.WriteLine("NO");
    }
}
  
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program to check if an array is
// subarray of another array
  
  
// Function to check if an array is
// subarray of another array
function isSubArray(A, B, n,m)
{
    // Two pointers to traverse the arrays
    var 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;
}
  
var A = [ 2, 3, 0, 5, 1, 1, 2 ];
var n = A.length;
var B = [ 3, 0, 5, 1 ];
var m =B.length;
if (isSubArray(A, B, n, m))
        document.write( "YES<br>");
    else
        document.write( "NO<br>");
          
// This code is contributed by SoumikMondal
</script>
Producción: 

YES

 

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array

Publicación traducida automáticamente

Artículo escrito por Kushdeep_Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *