String más corta formada por la concatenación de strings A x veces y B y veces tal que n(A)*x = n(B)*y

Dadas dos strings A y   B , la tarea es encontrar la string más corta que sea un múltiplo de A y B . Se dice que una string X es un múltiplo de la string Y si la string X se puede formar mediante la concatenación de múltiples ocurrencias de la string Y.

Ejemplo:

Entrada : A = “aaa”, B= “aa”
Salida : aaaaaa
Explicación: Multiplicar A dos veces y B tres veces resultará en aaaaaa

Entrada: A=”frío”, B =”viejo”
Salida: -1

 

Enfoque: El problema dado se puede resolver basándose en la observación de que la longitud de la string más pequeña que puede ser un múltiplo de las strings A y B debe ser igual al MCM de la longitud de A y la longitud de B. Por lo tanto, el problema dado se puede resolver siguiendo los siguientes pasos:

  • Cree una variable lcm , que almacene el valor LCM de la longitud de A y la longitud de B .
  • Cree una string C que se forme después de concatenar la string A , lcm / (longitud de A) veces.
  • De manera similar, cree una string D que se forme después de concatenar la string B , lcm / (longitud de B) veces.
  • Compruebe si las strings C y D son iguales o no. Si lo son, imprima cualquiera de ellos; de lo contrario, imprima -1 .

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 GCD of two numbers
int gcd(int a, int b)
{
    if (a == 0) {
        return b;
    }
    return gcd(b % a, a);
}
 
// Function to find shortest string that
// is a multiple of string A and B
void ShortestString(string A, string B)
{
    int n1 = A.length();
    int n2 = B.length();
    int g = gcd(n1, n2);
 
    // Stores the Lcm of length
    // of string A and B
    int lcm = (n1 * n2) / g;
 
    // Stores multiple of string A
    string C = "";
 
    // Stores multiple of string B
    string D = "";
 
    // Concatenate A, lcm / n1 times
    for (int i = 0; i < (lcm / n1); i++) {
        C = C + A;
    }
 
    // Concatenate B, lcm / n2 times
    for (int i = 0; i < (lcm / n2); i++) {
        D = D + B;
    }
 
    // If both strings are equal
    // to each other
    if (C == D) {
        cout << C;
    }
    else {
        cout << -1;
    }
}
 
// Driver Code
int main()
{
    string A = "aaa";
    string B = "aa";
    ShortestString(A, B);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find GCD of two numbers
static int gcd(int a, int b)
{
    if (a == 0) {
        return b;
    }
    return gcd(b % a, a);
}
 
// Function to find shortest String that
// is a multiple of String A and B
static void ShortestString(String A, String B)
{
    int n1 = A.length();
    int n2 = B.length();
    int g = gcd(n1, n2);
 
    // Stores the Lcm of length
    // of String A and B
    int lcm = (n1 * n2) / g;
 
    // Stores multiple of String A
    String C = "";
 
    // Stores multiple of String B
    String D = "";
 
    // Concatenate A, lcm / n1 times
    for (int i = 0; i < (lcm / n1); i++) {
        C = C + A;
    }
 
    // Concatenate B, lcm / n2 times
    for (int i = 0; i < (lcm / n2); i++) {
        D = D + B;
    }
 
    // If both Strings are equal
    // to each other
    if (C.equals(D)) {
        System.out.print(C);
    }
    else {
        System.out.print(-1);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    String A = "aaa";
    String B = "aa";
    ShortestString(A, B);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python code for the above approach
 
# Function to find GCD of two numbers
def gcd(a, b):
    if (a == 0):
        return b
    return gcd(b % a, a)
 
# Function to find shortest string that
# is a multiple of string A and B
def ShortestString(A, B):
    n1 = len(A)
    n2 = len(B)
    g = gcd(n1, n2)
 
    # Stores the Lcm of length
    # of string A and B
    lcm = (n1 * n2) / g
 
    # Stores multiple of string A
    C = ""
 
    # Stores multiple of string B
    D = ""
 
    # Concatenate A, lcm / n1 times
    for i in range(0, (int)(lcm//n1)):
        C = C + A
 
    # Concatenate B, lcm / n2 times
    for i in range((int)(lcm // n2)):
        D = D + B
 
    # If both strings are equal
    # to each other
    if (C == D):
        print(C)
    else:
        print(-1)
 
# Driver Code
A = "aaa"
B = "aa"
ShortestString(A, B)
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
class GFG{
 
// Function to find GCD of two numbers
static int gcd(int a, int b)
{
    if (a == 0) {
        return b;
    }
    return gcd(b % a, a);
}
 
// Function to find shortest String that
// is a multiple of String A and B
static void ShortestString(string A, string B)
{
    int n1 = A.Length;
    int n2 = B.Length;
    int g = gcd(n1, n2);
 
    // Stores the Lcm of length
    // of String A and B
    int lcm = (n1 * n2) / g;
 
    // Stores multiple of String A
    string C = "";
 
    // Stores multiple of String B
    string D = "";
 
    // Concatenate A, lcm / n1 times
    for (int i = 0; i < (lcm / n1); i++) {
        C = C + A;
    }
 
    // Concatenate B, lcm / n2 times
    for (int i = 0; i < (lcm / n2); i++) {
        D = D + B;
    }
 
    // If both Strings are equal
    // to each other
    if (C.Equals(D)) {
        Console.Write(C);
    }
    else {
        Console.Write(-1);
    }
}
 
// Driver Code
public static void Main()
{
    string A = "aaa";
    string B = "aa";
    ShortestString(A, B);
}
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
      // JavaScript code for the above approach
 
      // Function to find GCD of two numbers
      function gcd(a, b) {
          if (a == 0) {
              return b;
          }
          return gcd(b % a, a);
      }
 
      // Function to find shortest string that
      // is a multiple of string A and B
      function ShortestString(A, B) {
          let n1 = A.length;
          let n2 = B.length;
          let g = gcd(n1, n2);
 
          // Stores the Lcm of length
          // of string A and B
          let lcm = (n1 * n2) / g;
 
          // Stores multiple of string A
          let C = "";
 
          // Stores multiple of string B
          let D = "";
 
          // Concatenate A, lcm / n1 times
          for (let i = 0; i < (lcm / n1); i++) {
              C = C + A;
          }
 
          // Concatenate B, lcm / n2 times
          for (let i = 0; i < (lcm / n2); i++) {
              D = D + B;
          }
 
          // If both strings are equal
          // to each other
          if (C == D) {
              document.write(C);
          }
          else {
              document.write(-1);
          }
      }
 
      // Driver Code
      let A = "aaa";
      let B = "aa";
      ShortestString(A, B);
 
// This code is contributed by Potta Lokesh
  </script>
Producción

aaaaaa

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por prathamjha5683 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 *