El subarreglo común más largo en los dos arreglos dados

Posted on by Rudeus Greyrat

Dados dos arreglos A[] y B[] de N y M enteros respectivamente, la tarea es encontrar la longitud máxima del subarreglo igual o el subarreglo común más largo entre los dos arreglos dados .

Ejemplos: 

Entrada: A[] = {1, 2, 8, 2, 1}, B[] = {8, 2, 1, 4, 7} 
Salida: 3 
Explicación: 
El subarreglo que es común a ambos arreglos es {8, 2, 1} y la longitud del subarreglo es 3.
Entrada: A[] = {1, 2, 3, 2, 1}, B[] = {8, 7, 6, 4, 7} 
Salida: 0 
Explicación : 
No existen tales subarreglos que sean iguales en el arreglo A[] y B[]. 

Enfoque ingenuo: la idea es generar todos los subarreglos de los dos arreglos dados A[] y B[] y encontrar el subarreglo coincidente más largo. Esta solución es exponencial en términos de complejidad temporal.
Complejidad de tiempo: O(2 N+M ), donde N es la longitud de la array A[] y M es la longitud de la array B[] .

Enfoque eficiente: 
el enfoque eficiente es utilizar la programación dinámica (DP) . Este problema es la variación de la subsecuencia común más larga (LCS) . 
Deje que las secuencias de entrada sean A[0..n-1] y B[0..m-1] de longitudes m y n respectivamente. A continuación se muestra la implementación recursiva de los subarreglos iguales: 

  1. Dado que el subarreglo común de A[] y B[] debe comenzar en algún índice i y j tal que A[i] sea igual a B[j] . Sea dp[i][j] el subarreglo común más largo de A[i…] y B[j…] .
  2. Por lo tanto, para cualquier índice i y j, si A[i] es igual a B[j], entonces dp[i][j] = dp[i+1][j+1] + 1 .
  3. El máximo de todos los elementos en la array dp[][] dará la longitud máxima de subarreglos iguales.

Por ejemplo: 
si la array dada A[] = {1, 2, 8, 2, 1} y B[] = {8, 2, 1, 4, 7}. Si los caracteres coinciden en el índice i y j para la array A[] y B[] respectivamente, entonces dp[i][j] se actualizará como 1 + dp[i+1][j+1] . A continuación se muestra la tabla dp[][]
actualizada para la array dada A[] y B[] . 

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to DP approach
// to above solution
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// length of equal subarray
int FindMaxLength(int A[], int B[], int n, int m)
{
 
    // Auxiliary dp[][] array
    int dp[n + 1][m + 1];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = 0;
 
    // Updating the dp[][] table
    // in Bottom Up approach
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = m - 1; j >= 0; j--)
        {
            // If A[i] is equal to B[i]
            // then dp[j][i] = dp[j + 1][i + 1] + 1
            if (A[i] == B[j])
                dp[j][i] = dp[j + 1][i + 1] + 1;
        }
    }
    int maxm = 0;
 
    // Find maximum of all the values
    // in dp[][] array to get the
    // maximum length
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            // Update the length
            maxm = max(maxm, dp[i][j]);
        }
    }
 
    // Return the maximum length
    return maxm;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 2, 8, 2, 1 };
    int B[] = { 8, 2, 1, 4, 7 };
 
    int n = sizeof(A) / sizeof(A[0]);
    int m = sizeof(B) / sizeof(B[0]);
 
    // Function call to find
    // maximum length of subarray
    cout << (FindMaxLength(A, B, n, m));
}
 
// This code is contributed by chitranayal

Java

// Java program to DP approach
// to above solution
class GFG
{
    // Function to find the maximum
    // length of equal subarray
    static int FindMaxLength(int A[], int B[], int n, int m)
    {
 
        // Auxiliary dp[][] array
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i][j] = 0;
 
        // Updating the dp[][] table
        // in Bottom Up approach
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--)
            {
                // If A[i] is equal to B[i]
                // then dp[j][i] = dp[j + 1][i + 1] + 1
                if (A[i] == B[j])
                    dp[j][i] = dp[j + 1][i + 1] + 1;
            }
        }
        int maxm = 0;
 
        // Find maximum of all the values
        // in dp[][] array to get the
        // maximum length
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                // Update the length
                maxm = Math.max(maxm, dp[i][j]);
            }
        }
 
        // Return the maximum length
        return maxm;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A[] = { 1, 2, 8, 2, 1 };
        int B[] = { 8, 2, 1, 4, 7 };
 
        int n = A.length;
        int m = B.length;
 
        // Function call to find
        // maximum length of subarray
        System.out.print(FindMaxLength(A, B, n, m));
    }
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python program to DP approach
# to above solution
 
# Function to find the maximum
# length of equal subarray
 
 
def FindMaxLength(A, B):
    n = len(A)
    m = len(B)
 
    # Auxiliary dp[][] array
    dp = [[0 for i in range(n + 1)] for i in range(m + 1)]
 
    # Updating the dp[][] table
    # in Bottom Up approach
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
 
            # If A[i] is equal to B[i]
            # then dp[j][i] = dp[j + 1][i + 1] + 1
            if A[i] == B[j]:
                dp[j][i] = dp[j + 1][i + 1] + 1
    maxm = 0
 
    # Find maximum of all the values
    # in dp[][] array to get the
    # maximum length
    for i in dp:
        for j in i:
 
            # Update the length
            maxm = max(maxm, j)
 
    # Return the maximum length
    return maxm
 
 
# Driver Code
if __name__ == '__main__':
    A = [1, 2, 8, 2, 1]
    B = [8, 2, 1, 4, 7]
 
    # Function call to find
    # maximum length of subarray
    print(FindMaxLength(A, B))

C#

// C# program to DP approach
// to above solution
using System;
 
class GFG
{
    // Function to find the maximum
    // length of equal subarray
    static int FindMaxLength(int[] A, int[] B, int n, int m)
    {
 
        // Auxiliary [,]dp array
        int[, ] dp = new int[n + 1, m + 1];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i, j] = 0;
 
        // Updating the [,]dp table
        // in Bottom Up approach
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--)
            {
                // If A[i] is equal to B[i]
                // then dp[j, i] = dp[j + 1, i + 1] + 1
                if (A[i] == B[j])
                    dp[j, i] = dp[j + 1, i + 1] + 1;
            }
        }
        int maxm = 0;
 
        // Find maximum of all the values
        // in [,]dp array to get the
        // maximum length
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
 
                // Update the length
                maxm = Math.Max(maxm, dp[i, j]);
            }
        }
 
        // Return the maximum length
        return maxm;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] A = { 1, 2, 8, 2, 1 };
        int[] B = { 8, 2, 1, 4, 7 };
 
        int n = A.Length;
        int m = B.Length;
 
        // Function call to find
        // maximum length of subarray
        Console.Write(FindMaxLength(A, B, n, m));
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript program to DP approach
// to above solution
     
    // Function to find the maximum
    // length of equal subarray
    function FindMaxLength(A,B,n,m)
    {
        // Auxiliary dp[][] array
        let dp = new Array(n + 1);
        for (let i = 0; i <= n; i++)
        {
            dp[i]=new Array(m+1);
            for (let j = 0; j <= m; j++)
                dp[i][j] = 0;
         }
        // Updating the dp[][] table
        // in Bottom Up approach
        for (let i = n - 1; i >= 0; i--)
        {
            for (let j = m - 1; j >= 0; j--)
            {
                // If A[i] is equal to B[i]
                // then dp[j][i] = dp[j + 1][i + 1] + 1
                if (A[i] == B[j])
                    dp[j][i] = dp[j + 1][i + 1] + 1;
            }
        }
        let maxm = 0;
  
        // Find maximum of all the values
        // in dp[][] array to get the
        // maximum length
        for (let i = 0; i < n; i++)
        {
            for (let j = 0; j < m; j++)
            {
                // Update the length
                maxm = Math.max(maxm, dp[i][j]);
            }
        }
  
        // Return the maximum length
        return maxm;
    }
     
    // Driver Code
    let A=[1, 2, 8, 2, 1 ];
    let B=[8, 2, 1, 4, 7];
    let n = A.length;
    let m = B.length;
     
    // Function call to find
        // maximum length of subarray
    document.write(FindMaxLength(A, B, n, m));
     
     
     
// This code is contributed by avanitrachhadiya2155
</script>
Producción

3

Complejidad de tiempo: O(N*M), donde N es la longitud de la array A[] y M es la longitud de la array B[].
Espacio auxiliar: O(N*M)

Publicación traducida automáticamente

Artículo escrito por mohit kumar 29 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 *