Dadas dos strings S y T de longitud N y M respectivamente, la tarea es encontrar la string más pequeña que sea divisible por ambas strings. Si no existe tal string, imprima -1 .
Para dos strings A y B cualesquiera , B divide a A si y solo si A es la concatenación de B al menos una vez.
Ejemplos:
Entrada: S = “abab”, T = “ab”
Salida: abab
Explicación: La string “abab” es la misma que S y el doble de la concatenación de la string T (“abab” = “ab” + “ab” = T + T)Entrada: S = “ccc”, T = “cc”
Salida: cccccc
Explicación: La string “cccccc” es una concatenación de S y T dos y tres veces respectivamente.
(“cccccc” = “ccc” + “ccc” = S + S)
(“cccccc” = “cc” + “cc” + “cc” = T + T + T)
Enfoque: La idea se basa en la observación de que la longitud de la string requerida, por ejemplo, L, debe ser igual al mínimo común múltiplo de N y M. Compruebe si la string S concatenada L / N número de veces es igual a la string T concatenada L / M número de veces o no. Si se encuentra que es cierto, imprima cualquiera de ellos. De lo contrario, imprima -1 . Siga los pasos a continuación para resolver el problema:
- Almacene el mínimo común múltiplo de N y M en una variable, digamos L .
- Inicialice dos strings S1 y T1 .
- Concatene la string, S1 con la string, S , (L/N) número de veces .
- Concatene la string, T1 con la string, T , (L/M) número de veces .
- Si las strings S1 y T1 son iguales , imprima S1 como resultado.
- 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 calculate
// GCD of two numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate
// LCM of two numbers
int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
// Function to find the smallest string
// which is divisible by strings S and T
void findSmallestString(string s, string t)
{
// Store the length of both strings
int n = s.length(), m = t.length();
// Store LCM of n and m
int l = lcm(n, m);
// Temporary strings to store
// concatenated strings
string s1 = "", t1 = "";
// Concatenate s1 (l / n) times
for (int i = 0; i < l / n; i++) {
s1 += s;
}
// Concatenate t1 (l / m) times
for (int i = 0; i < l / m; i++) {
t1 += t;
}
// If s1 and t1 are equal
if (s1 == t1)
cout << s1;
// Otherwise, print -1
else
cout << -1;
}
// Driver Code
int main()
{
string S = "baba", T = "ba";
findSmallestString(S, T);
return 0;
}
Java
// Java program for above approach
import java.io.*;
class GFG
{
// Function to calculate
// GCD of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate
// LCM of two numbers
static int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
// Function to find the smallest string
// which is divisible by strings S and T
static void findSmallestString(String s, String t)
{
// Store the length of both strings
int n = s.length(), m = t.length();
// Store LCM of n and m
int l = lcm(n, m);
// Temporary strings to store
// concatenated strings
String s1 = "", t1 = "";
// Concatenate s1 (l / n) times
for (int i = 0; i < l / n; i++) {
s1 += s;
}
// Concatenate t1 (l / m) times
for (int i = 0; i < l / m; i++) {
t1 += t;
}
// If s1 and t1 are equal
if (s1.equals(t1)){
System.out.println(s1);
}
// Otherwise, print -1
else{
System.out.println(-1);
}
}
// Driver code
public static void main(String[] args)
{
String S = "baba", T = "ba";
findSmallestString(S, T);
}
}
// This code is contributed by susmitakundugoaldanga.
Python3
# Python3 program for the above approach # Function to calculate # GCD of two numbers def gcd(a, b): if (b == 0): return a return gcd(b, a % b) # Function to calculate # LCM of two numbers def lcm(a, b): return (a // gcd(a, b)) * b # Function to find the smallest string # which is divisible by strings S and T def findSmallestString(s, t): # Store the length of both strings n, m = len(s), len(t) # Store LCM of n and m l = lcm(n, m) # Temporary strings to store # concatenated strings s1, t1 = "", "" # Concatenate s1 (l / n) times for i in range(l//n): s1 += s # Concatenate t1 (l / m) times for i in range(l//m): t1 += t # If s1 and t1 are equal if (s1 == t1): print(s1) # Otherwise, pr-1 else: print(-1) # Driver Code if __name__ == '__main__': S, T = "baba", "ba" findSmallestString(S, T) # This code is contributed by mohit kumar 29.
C#
// C# program for above approach
using System;
public class GFG
{
// Function to calculate
// GCD of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate
// LCM of two numbers
static int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
// Function to find the smallest string
// which is divisible by strings S and T
static void findSmallestString(string s, string t)
{
// Store the length of both strings
int n = s.Length, m = t.Length;
// Store LCM of n and m
int l = lcm(n, m);
// Temporary strings to store
// concatenated strings
string s1 = "", t1 = "";
// Concatenate s1 (l / n) times
for (int i = 0; i < l / n; i++) {
s1 += s;
}
// Concatenate t1 (l / m) times
for (int i = 0; i < l / m; i++) {
t1 += t;
}
// If s1 and t1 are equal
if (s1 == t1)
Console.WriteLine(s1);
// Otherwise, print -1
else
Console.WriteLine(-1);
}
// Driver code
public static void Main(String[] args)
{
string S = "baba", T = "ba";
findSmallestString(S, T);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for above approach
// Function to calculate
// GCD of two numbers
function gcd(a,b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to calculate
// LCM of two numbers
function lcm(a,b)
{
return (a / gcd(a, b)) * b;
}
// Function to find the smallest string
// which is divisible by strings S and T
function findSmallestString(s,t)
{
// Store the length of both strings
let n = s.length, m = t.length;
// Store LCM of n and m
let l = lcm(n, m);
// Temporary strings to store
// concatenated strings
let s1 = "", t1 = "";
// Concatenate s1 (l / n) times
for (let i = 0; i < l / n; i++) {
s1 += s;
}
// Concatenate t1 (l / m) times
for (let i = 0; i < l / m; i++) {
t1 += t;
}
// If s1 and t1 are equal
if (s1 == (t1)){
document.write(s1+"<br>");
}
// Otherwise, print -1
else{
document.write(-1+"<br>");
}
}
// Driver code
let S = "baba", T = "ba";
findSmallestString(S, T);
// This code is contributed by unknown2108
</script>
baba
Complejidad de tiempo: O(max(N, M))
Espacio auxiliar: O(max(N, M))
Publicación traducida automáticamente
Artículo escrito por NalinGoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA