Dadas dos arrays A[] y B[] que consisten en 
y 
nú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>
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