Dadas dos strings binarias A y B de tamaño N y M respectivamente, la tarea es maximizar el valor de la longitud de (X) / 2 XOR(X, Y) eligiendo dos substrings X e Y de igual longitud de la string dada A y B respectivamente.
Ejemplos:
Entrada: A = “0110”, B = “1101”
Salida: 3
Explicación:
Elija la substring “110” y “110” de la string A y B respectivamente. El valor de la expresión de longitud (X) / 2 XOR (X, Y) es 3 / 2 0 = 3, que es el máximo entre todas las combinaciones posibles.Entrada: A = “1111”, B = “0000”
Salida: 0
Enfoque: el problema dado se puede resolver observando la expresión que necesita ser maximizada, por lo tanto, el denominador debe ser mínimo , y para minimizarlo, el valor de Bitwise XOR de las substrings X e Y debe ser mínimo, es decir, cero y para hacer el valor de Bitwise XOR como cero , las dos substrings deben ser iguales. Por lo tanto, el problema se reduce a encontrar la substring común más larga de las strings A y B. Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D , diga LCSuff[M + 1][N + 1] para almacenar las longitudes de los sufijos comunes más largos de las substrings .
- Inicialice una variable, diga resultado como 0 para almacenar el valor máximo del resultado de la expresión dada.
- Iterar sobre el rango [0, M] usando la variable i e iterar anidado sobre el rango [0, N] usando la variable j y realizar los siguientes pasos:
- Si i es igual a 0 o j es igual a 0 , actualice el valor de LCSSuff[i][j] es igual a 0 .
- De lo contrario, si el valor de A[i – 1] es igual a A[j – 1] , actualice el valor de LCSSuff[i][j] como LCSSuff[i – 1][j – 1] + 1 y actualice el valor de resultado como el máximo de resultado y LCSSuff[i][j] .
- De lo contrario, actualice el valor de LCSSuff[i][j] a 0 .
- Después de completar los pasos anteriores, imprima el valor de resultado como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of the
// longest common substring of the
// string X and Y
int LCSubStr(char* A, char* B, int m, int n)
{
// LCSuff[i][j] stores the lengths
// of the longest common suffixes
// of substrings
int LCSuff[m + 1][n + 1];
int result = 0;
// Iterate over strings A and B
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// If first row or column
if (i == 0 || j == 0)
LCSuff[i][j] = 0;
// If matching is found
else if (A[i - 1] == B[j - 1]) {
LCSuff[i][j]
= LCSuff[i - 1][j - 1]
+ 1;
result = max(result,
LCSuff[i][j]);
}
// Otherwise, if matching
// is not found
else
LCSuff[i][j] = 0;
}
}
// Finally, return the resultant
// maximum value LCS
return result;
}
// Driver Code
int main()
{
char A[] = "0110";
char B[] = "1101";
int M = strlen(A);
int N = strlen(B);
// Function Call
cout << LCSubStr(A, B, M, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the length of the
// longest common substring of the
// string X and Y
static int lcsubtr(char a[], char b[], int length1,
int length2)
{
// LCSuff[i][j] stores the lengths
// of the longest common suffixes
// of substrings
int dp[][] = new int[length1 + 1][length2 + 1];
int max = 0;
// Iterate over strings A and B
for(int i = 0; i <= length1; ++i)
{
for(int j = 0; j <= length2; ++j)
{
// If first row or column
if (i == 0 || j == 0)
{
dp[i][j] = 0;
}
// If matching is found
else if (a[i - 1] == b[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
max = Math.max(dp[i][j], max);
}
// Otherwise, if matching
// is not found
else
{
dp[i][j] = 0;
}
}
}
// Finally, return the resultant
// maximum value LCS
return max;
}
// Driver Code
public static void main(String[] args)
{
String m = "0110";
String n = "1101";
char m1[] = m.toCharArray();
char m2[] = n.toCharArray();
// Function Call
System.out.println(lcsubtr(m1, m2, m1.length,
m2.length));
}
}
// This code is contributed by zack_aayush
Python3
# Python 3 program for the above approach # Function to find the length of the # longest common substring of the # string X and Y def LCSubStr(A, B, m, n): # LCSuff[i][j] stores the lengths # of the longest common suffixes # of substrings LCSuff = [[0 for i in range(n+1)] for j in range(m+1)] result = 0 # Iterate over strings A and B for i in range(m + 1): for j in range(n + 1): # If first row or column if (i == 0 or j == 0): LCSuff[i][j] = 0 # If matching is found elif(A[i - 1] == B[j - 1]): LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1 result = max(result,LCSuff[i][j]) # Otherwise, if matching # is not found else: LCSuff[i][j] = 0 # Finally, return the resultant # maximum value LCS return result # Driver Code if __name__ == '__main__': A = "0110" B = "1101" M = len(A) N = len(B) # Function Call print(LCSubStr(A, B, M, N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the length of the
// longest common substring of the
// string X and Y
static int lcsubtr(char[] a, char[] b, int length1,
int length2)
{
// LCSuff[i][j] stores the lengths
// of the longest common suffixes
// of substrings
int[,] dp = new int[length1 + 1, length2 + 1];
int max = 0;
// Iterate over strings A and B
for(int i = 0; i <= length1; ++i)
{
for(int j = 0; j <= length2; ++j)
{
// If first row or column
if (i == 0 || j == 0)
{
dp[i, j] = 0;
}
// If matching is found
else if (a[i - 1] == b[j - 1])
{
dp[i, j] = dp[i - 1, j - 1] + 1;
max = Math.Max(dp[i, j], max);
}
// Otherwise, if matching
// is not found
else
{
dp[i, j] = 0;
}
}
}
// Finally, return the resultant
// maximum value LCS
return max;
}
// Driver Code
public static void Main()
{
string m = "0110";
string n = "1101";
char[] m1 = m.ToCharArray();
char[] m2 = n.ToCharArray();
// Function Call
Console.Write(lcsubtr(m1, m2, m1.Length,
m2.Length));
}
}
// This code is contributed by target_2.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the length of the
// longest common substring of the
// string X and Y
function LCSubStr(A, B, m, n)
{
// LCSuff[i][j] stores the lengths
// of the longest common suffixes
// of substrings
let LCSuff = Array(m + 1).fill(Array(n + 1));
let result = 0;
// Iterate over strings A and B
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
// If first row or column
if (i == 0 || j == 0)
LCSuff[i][j] = 0;
// If matching is found
else if (A.charAt(i - 1) == B.charAt(j - 1)) {
LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;
if (LCSuff[i][j] > result) {
result = LCSuff[i][j];
}
}
// Otherwise, if matching
// is not found
else
LCSuff[i][j] = 0;
}
}
result++;
// Finally, return the resultant
// maximum value LCS
return result;
}
// Driver Code
let A = "0110";
let B = "1101";
let M = A.length;
let N = B.length;
// Function Call
document.write(LCSubStr(A, B, M, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad temporal: O(M*N)
Espacio auxiliar: O(M*N)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA