Maximice la función dada seleccionando substrings de igual longitud de strings binarias dadas

Dadas dos strings binarias s1 y s2 . La tarea es elegir una substring de s1 y s2 , digamos sub1 y sub2 de igual longitud, de modo que maximice la función:

diversión(s1, s2) = len(sub1) / (2 ^{xor(sub1, sub2)} )

Ejemplos:

Entrada: s1= “1101”, s2= “1110”
Salida: 3
Explicación: A continuación se encuentran las substrings elegidas de s1 y s2
Substring elegida de s1 -> “110”
Substring elegida de s2 -> “110”
Por lo tanto, fun(s1 , s2) = 3/ (2 ^{xor(110, 110)} ) = 3, que es el máximo posible. 

Entrada: s1= “1111”, s2= “1000”
Salida: 1

Enfoque: con el fin de maximizar la función dada, era necesario elegir substrings grandes con un XOR mínimo. Para minimizar el denominador, elija substrings de manera que XOR de sub1 y sub2 sea siempre 0 , de modo que el término del denominador siempre sea 1 (2 ⁰ ). Entonces, para eso, busque la substring común más larga de las dos strings s1 y s2 e imprima su longitud, que sería la respuesta requerida. 

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
int dp[1000][1000];
 
// Function to find longest common substring.
int lcs(string s, string k, int n, int m)
{
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 or j == 0) {
                dp[i][j] = 0;
            }
            else if (s[i - 1] == k[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }
            else {
                dp[i][j] = max(dp[i - 1][j],
                               dp[i][j - 1]);
            }
        }
    }
 
    // Return the result
    return dp[n][m];
}
 
// Driver Code
int main()
{
    string s1 = "1110";
    string s2 = "1101";
 
    cout << lcs(s1, s2,
                s1.size(), s2.size());
 
    return 0;
}

// Java program for above approach
class GFG{
   
  static int dp[][] = new int[1000][1000];
 
  // Function to find longest common substring.
  static int lcs(String s, String k, int n, int m)
  {
      for (int i = 0; i <= n; i++) {
          for (int j = 0; j <= m; j++) {
              if (i == 0 || j == 0) {
                  dp[i][j] = 0;
              }
              else if (s.charAt(i - 1) == k.charAt(j - 1)) {
                  dp[i][j] = 1 + dp[i - 1][j - 1];
              }
              else {
                  dp[i][j] = Math.max(dp[i - 1][j],
                                 dp[i][j - 1]);
              }
          }
      }
 
      // Return the result
      return dp[n][m];
  }
 
  // Driver Code
  public static void main(String [] args)
  {
      String s1 = "1110";
      String s2 = "1101";
 
      System.out.print(lcs(s1, s2,
                  s1.length(), s2.length()));
 
       
  }
}
 
// This code is contributed by AR_Gaurav

# Python3 program for above approach
 
import numpy as np;
 
dp = np.zeros((1000,1000));
 
# Function to find longest common substring.
def lcs( s,  k,  n,  m) :
 
    for i in range(n + 1) :
        for j in range(m + 1) :
            if (i == 0 or j == 0) :
                dp[i][j] = 0;
             
            elif (s[i - 1] == k[j - 1]) :
                dp[i][j] = 1 + dp[i - 1][j - 1];
             
            else :
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
 
    # Return the result
    return dp[n][m];
 
# Driver Code
if __name__ == "__main__" :
 
    s1 = "1110";
    s2 = "1101";
 
    print(lcs(s1, s2,len(s1), len(s2)));
 
   # This code is contributed by AnkThon

// C# program for above approach
using System;
public class GFG{
   
  static int [,]dp = new int[1000,1000];
 
  // Function to find longest common substring.
  static int lcs(string s, string k, int n, int m)
  {
      for (int i = 0; i <= n; i++) {
          for (int j = 0; j <= m; j++) {
              if (i == 0 || j == 0) {
                  dp[i, j] = 0;
              }
              else if (s[i - 1] == k[j - 1]) {
                  dp[i, j] = 1 + dp[i - 1, j - 1];
              }
              else {
                  dp[i, j] = Math.Max(dp[i - 1, j],
                                 dp[i, j - 1]);
              }
          }
      }
 
      // Return the result
      return dp[n, m];
  }
 
  // Driver Code
  public static void Main(string [] args)
  {
      string s1 = "1110";
      string s2 = "1101";
 
      Console.Write(lcs(s1, s2, s1.Length, s2.Length));
  }
}
 
// This code is contributed by AnkThon

<script>
// JavaScript program for above approach
var dp = new Array(1000);
for (var i = 0; i < 1000; i++) {
  dp[i] = new Array(1000);
}
     
// Function to find longest common substring.
function lcs( s,  k,  n,  m)
{
    for (var i = 0; i <= n; i++) {
        for (var j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            }
            else if (s[i - 1] == k[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }
            else {
                dp[i][j] = Math.max(dp[i - 1][j],
                               dp[i][j - 1]);
            }
        }
    }
 
    // Return the result
    return dp[n][m];
}
 
// Driver Code
var s1 = "1110";
var s2 = "1101";
 
document.write(lcs(s1, s2, s1.length, s2.length))
 
// This code is contributed by AnkThon
</script>

3

Complejidad de tiempo: O(N*M), donde N es el tamaño de s1 y M es el tamaño de s2.

Espacio auxiliar: O(N*M), donde N es el tamaño de s1 y M es el tamaño de s2.