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 aaaaaaEntrada: 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>
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