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