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