Encuentre la string binaria más corta que contenga una o más ocurrencias de strings dadas

Dadas dos strings binarias , S1 y S2 , la tarea es generar una nueva string binaria (de la menor longitud posible) que se puede establecer como una o más ocurrencias de S1 y S2 . Si no es posible generar tal string , devuelva -1 en la salida. Tenga en cuenta que la string resultante no debe tener strings incompletas S1 o S2.

Por ejemplo, «1111» puede ser la string resultante de «11» y «1111» , ya que es una aparición de «1111» y también se puede juzgar como dos apariciones de «11» .

Ejemplos:

Entrada: S1 = “1010”, S2 = “101010”
Salida: 101010101010
Explicación: La string resultante tiene 3 ocurrencias de s1 y 2 ocurrencias de s2.

Entrada: S1 = “000”, S2 = “101”
Salida: -1
Explicación: No hay forma posible de construir una string de este tipo.

Enfoque: si es posible hacer una string de este tipo , entonces su longitud será el MCM de las longitudes de las strings S1 y S2 . Porque solo entonces, se puede establecer como un múltiplo mínimo de la string S1 y S2 . Siga los pasos a continuación para resolver el problema:

• Defina una función repeat(int k, string S) y realice las siguientes tareas:
  • Inicialice la string r como una string vacía .
  • Iterar sobre el rango [0, K] y realizar los siguientes pasos:
    • Agregue la string S a la variable r.
  • Devuelve la string r como respuesta.
• Inicialice las variables x e y como las longitudes de las strings S1 y S2.
• Inicialice la variable gcd como el MCD de x e y.
• Llame a la función repeat(y/gcd, s1) para formar la string S1 tantas veces y guárdela en la variable A .
• Llama a la función repeat(x/gcd, s2) para formar la string S2 tantas veces como quieras y guárdala en la variable B .
• Si A es igual a B, escriba cualquiera de ellos como respuesta, de lo contrario escriba «NO».

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to form the resultant string
string repeat(int k, string S)
{
    string r = "";
    while (k--) {
        r += S;
    }
    return r;
}
 
// Function to find if any such string
// exists or not. If yes, find it
void find(string s1, string s2)
{
    int x = s1.size(), y = s2.size();
 
    // GCD of x and y
    int gcd = __gcd(x, y);
 
    // Form the resultant strings
    string A = repeat(y / gcd, s1);
    string B = repeat(x / gcd, s2);
 
    // If both the strings are same,
    // then print the answer
    if (A == B) {
        cout << A;
    }
    else {
        cout << "-1";
    }
}
 
// Driver Code
int main()
{
 
    // Initializing strings
    string s1 = "1010", s2 = "101010";
 
    find(s1, s2);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG {
    public static int GCD(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return GCD(a - b, b);
        return GCD(a, b - a);
    }
 
    public static String repeat(int k, String S)
    {
        String r = "";
        while (k--!=0) {
            r += S;
        }
        return r;
    }
 
    // Function to find if any such string
    // exists or not. If yes, find it
    public static void find(String s1, String s2)
    {
        int x = s1.length(), y = s2.length();
 
        // GCD of x and y
        int gcd = GCD(x, y);
 
        // Form the resultant strings
        String A = repeat(y / gcd, s1);
        String B = repeat(x / gcd, s2);
 
        // If both the strings are same,
        // then print the answer
        if (A.equals(B)) {
            System.out.println(A);
        }
        else {
            System.out.println("-1");
        }
    }
 
    // Driver Code
 
    public static void main(String[] args)
    {
       
        // Initializing strings
        String s1 = "1010", s2 = "101010";
 
        find(s1, s2);
    }
}
 
// This code is contributed by maddler.

# Python program for the above approach
import math
 
# Function to form the resultant string
def repeat(k, S):
    r = ""
    while (k):
        r += S
        k-=1
    return r
 
 
# Function to find if any such string
# exists or not. If yes, find it
def find(s1, s2):
     
    x = len(s1)
    y = len(s2)
     
    # GCD of x and y
    gcd = math.gcd(x, y)
     
    # Form the resultant strings
    A = repeat(y // gcd, s1)
    B = repeat(x // gcd, s2)
     
    # If both the strings are same,
    # then print answer
    if (A == B):
        print(A)
    else:
        print("-1")
 
# Driver Code
 
# Initializing strings
s1 = "1010"
s2 = "101010"
 
find(s1, s2)
 
 
# This code is contributed by shivanisinghss2110

// C# program for the above approach
using System;
 
class GFG{
 
    public static int GCD(int a, int b)
    {
       
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return GCD(a - b, b);
        return GCD(a, b - a);
    }
 
    public static string repeat(int k, string S)
    {
        string r = "";
        while (k--!=0) {
            r += S;
        }
        return r;
    }
 
    // Function to find if any such string
    // exists or not. If yes, find it
    public static void find(string s1, string s2)
    {
        int x = s1.Length, y = s2.Length;
 
        // GCD of x and y
        int gcd = GCD(x, y);
 
        // Form the resultant strings
        string A = repeat(y / gcd, s1);
        string B = repeat(x / gcd, s2);
 
        // If both the strings are same,
        // then print the answer
        if (A.Equals(B)) {
            Console.Write(A);
        }
        else {
            Console.Write("-1");
        }
    }
 
// Driver Code
public static void Main()
{
    // Initializing strings
        string s1 = "1010", s2 = "101010";
 
        find(s1, s2);
}
}
 
// This code is contributed by code_hunt.

<script>
 
// Javascript program for the above approach
function GCD(a, b)
{
     
    // Everything divides 0
    if (a == 0)
        return b;
    if (b == 0)
        return a;
 
    // Base case
    if (a == b)
        return a;
         
    // a is greater
    if (a > b)
        return GCD(a - b, b);
         
    return GCD(a, b - a);
}
 
// Function to form the resultant string
function repeat(k, S)
{
    var r = "";
    while (k-- != 0)
    {
        r += S;
    }
    return r;
}
 
// Function to find if any such string
// exists or not. If yes, find it
function find(s1, s2)
{
    var x = s1.length, y = s2.length;
 
    // GCD of x and y
    var gcd = GCD(x, y);
 
    // Form the resultant strings
    var A = repeat(y / gcd, s1);
    var B = repeat(x / gcd, s2);
 
    // If both the strings are same,
    // then print the answer
    if (A == B)
    {
        document.write(A);
    }
    else
    {
        document.write("-1");
    }
}
 
// Driver Code
 
// Initializing strings
var s1 = "1010", s2 = "101010";
 
find(s1, s2);
 
// This code is contributed by shivanisinghss2110
 
</script>

101010101010

Complejidad de tiempo: O(m + n + log(max(m, n)))
Espacio auxiliar: O(n) (Para almacenar las strings A y B)