Dada una array de strings arr[] , la tarea es el máximo común divisor de la array de strings dada.
En las strings ‘A’ y ‘B’ , decimos que «B divide a A» si y solo si A = concatenación de B más de 1 vez. Encuentre la string más grande que divide tanto a A como a B.
Ejemplos:
Entrada: arr[] = { “GFGGFG”, “GFGGFG”, “GFGGFGGFGGFG” }
Salida: “GFGGFG”
Explicación:
“GFGGFG” es la string más grande que divide todos los elementos de la array.
Entrada: arr = { «Geeks», = «GFG»}
Salida: «»
Enfoque: La idea es utilizar la recursividad . A continuación se muestran los pasos:
- Cree una función recursiva gcd(str1, str2) .
- Si la longitud de str2 es mayor que str1 , repetiremos con gcd(str2, str1) .
- Ahora, si str1 no comienza con str2 , devuelve una string vacía.
- Si la string más larga comienza con una string más corta, corte la parte del prefijo común de la string más larga y recurra o repita hasta que una quede vacía.
- La string devuelta después de los pasos anteriores es el gcd de la array de string dada.
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 that finds gcd of 2 strings
string gcd(string str1, string str2)
{
// If str1 length is less than
// that of str2 then recur
// with gcd(str2, str1)
if (str1.length() < str2.length())
{
return gcd(str2, str1);
}
// If str1 is not the
// concatenation of str2
else if(str1.find(str2) != 0)
{
return "";
}
else if (str2 == "")
{
// GCD string is found
return str1;
}
else
{
// Cut off the common prefix
// part of str1 & then recur
return gcd(str1.substr(str2.length()), str2);
}
}
// Function to find GCD of array of
// strings
string findGCD(string arr[], int n)
{
string result = arr[0];
for (int i = 1; i < n; i++)
{
result = gcd(result, arr[i]);
}
// Return the GCD of strings
return result;
}
// Driver Code
int main()
{
// Given array of strings
string arr[]={ "GFGGFG",
"GFGGFG",
"GFGGFGGFGGFG" };
int n = sizeof(arr)/sizeof(arr[0]);
// Function Call
cout << findGCD(arr, n);
}
// This code is contributed by pratham76.
Java
// Java program for the above approach
class GCD {
// Function that finds gcd of 2 strings
static String gcd(String str1, String str2)
{
// If str1 length is less than
// that of str2 then recur
// with gcd(str2, str1)
if (str1.length() < str2.length()) {
return gcd(str2, str1);
}
// If str1 is not the
// concatenation of str2
else if (!str1.startsWith(str2)) {
return "";
}
else if (str2.isEmpty()) {
// GCD string is found
return str1;
}
else {
// Cut off the common prefix
// part of str1 & then recur
return gcd(str1.substring(str2.length()),
str2);
}
}
// Function to find GCD of array of
// strings
static String findGCD(String arr[], int n)
{
String result = arr[0];
for (int i = 1; i < n; i++) {
result = gcd(result, arr[i]);
}
// Return the GCD of strings
return result;
}
// Driver Code
public static void
main(String[] args)
{
// Given array of strings
String arr[]
= new String[] { "GFGGFG",
"GFGGFG",
"GFGGFGGFGGFG" };
int n = arr.length;
// Function Call
System.out.println(findGCD(arr, n));
}
}
Python3
# Python3 program for the above approach # Function that finds gcd of 2 strings def gcd(str1, str2): # If str1 length is less than # that of str2 then recur # with gcd(str2, str1) if(len(str1) < len(str2)): return gcd(str2, str1) # If str1 is not the # concatenation of str2 elif(not str1.startswith(str2)): return "" elif(len(str2) == 0): # GCD string is found return str1 else: # Cut off the common prefix # part of str1 & then recur return gcd(str1[len(str2):], str2) # Function to find GCD of array of # strings def findGCD(arr, n): result = arr[0] for i in range(1, n): result = gcd(result, arr[i]) # Return the GCD of strings return result # Driver Code # Given array of strings arr = ["GFGGFG", "GFGGFG", "GFGGFGGFGGFG" ] n = len(arr) # Function Call print(findGCD(arr, n)) # This code is contributed by avanitrachhadiya2155
C#
// C# program for
// the above approach
using System;
class GFG{
// Function that finds gcd
// of 2 strings
static String gcd(String str1,
String str2)
{
// If str1 length is less than
// that of str2 then recur
// with gcd(str2, str1)
if (str1.Length < str2.Length)
{
return gcd(str2, str1);
}
// If str1 is not the
// concatenation of str2
else if (!str1.StartsWith(str2))
{
return "";
}
else if (str2.Length == 0)
{
// GCD string is found
return str1;
}
else
{
// Cut off the common prefix
// part of str1 & then recur
return gcd(str1.Substring(str2.Length),
str2);
}
}
// Function to find GCD
// of array of strings
static String findGCD(String []arr,
int n)
{
String result = arr[0];
for (int i = 1; i < n; i++)
{
result = gcd(result, arr[i]);
}
// Return the GCD of strings
return result;
}
// Driver Code
public static void Main(String[] args)
{
// Given array of strings
String []arr = new String[] {"GFGGFG",
"GFGGFG",
"GFGGFGGFGGFG"};
int n = arr.Length;
// Function Call
Console.WriteLine(findGCD(arr, n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function that finds gcd
// of 2 strings
function gcd(str1, str2)
{
// If str1 length is less than
// that of str2 then recur
// with gcd(str2, str1)
if (str1.length < str2.length)
{
return gcd(str2, str1);
}
// If str1 is not the
// concatenation of str2
else if (!str1.startsWith(str2))
{
return "";
}
else if (str2.length == 0)
{
// GCD string is found
return str1;
}
else
{
// Cut off the common prefix
// part of str1 & then recur
return gcd(str1.substr(str2.length), str2);
}
}
// Function to find GCD
// of array of strings
function findGCD(arr, n)
{
let result = arr[0];
for (let i = 1; i < n; i++)
{
result = gcd(result, arr[i]);
}
// Return the GCD of strings
return result;
}
// Given array of strings
let arr = ["GFGGFG", "GFGGFG", "GFGGFGGFGGFG"];
let n = arr.length;
// Function Call
document.write(findGCD(arr, n));
// This code is contributed by decode2207.
</script>
Producción:
GFGGFG
Complejidad de tiempo: O(N*log(B)), donde N es el número de strings y B es la longitud máxima de cualquier string en arr[].
Espacio Auxiliar: O(1)