Encuentre el GCD de una array formada por strings numéricas

Dada una array arr[] que consta de strings numéricas, la tarea es calcular el máximo común divisor de la array dada.

Considerando las strings ‘A’ y ‘B’ , “ B divide a A ” si y sólo si A es una concatenación de B más de una vez. Encuentra la string más grande que divide tanto a A como a B.

Ejemplos:

Entrada: arr[] = { “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: siga los pasos a continuación para resolver el problema:

• Calcule GCD de la longitud de todas las strings de la array dada, digamos GCD .
• Compruebe si todas las strings de la array dada se pueden formar concatenando la substring {arr[0][0], .., arr[0][GCD – 1]} cualquier número de veces o no. Si se encuentra que es cierto, imprima {arr[0][0], .., arr[0][GCD – 1]} .
• De lo contrario, imprima una string vacía.

A continuación se muestra la implementación del enfoque anterior:

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function
// to return gcd of A and B
int GCD(int lena, int lenb)
{
 
  if (lena == 0)
    return lenb;
 
  if (lenb == 0)
    return lena;
 
  // Base case
  if (lena == lenb)
    return lena;
 
  // Length of A is greater
  if (lena > lenb)
    return GCD(lena - lenb, lenb);
 
  return GCD(lena, lenb - lena);
}
 
// Calculate GCD
string StringGCD(string a, string b)
{
 
  // Store the GCD of the
  // length of the strings
  int gcd = GCD(a.size(), b.size());
  if (a.substr(0, gcd) == b.substr(0, gcd))
  {
    int x = ((int)b.size()/gcd);
    int y = ((int)a.size()/gcd);
    string r="",s="";
 
    while (x--) s += a;
    while (y--) r += b;
 
    if (s == r)
      return a.substr(0, gcd);
  }
  return "-1";
}
 
// Driver Code
int main()
{
  string a = "geeksgeeks";
  string b = "geeks";
 
  // Function call
  cout<<(StringGCD(a, b));
}
 
// This code is contributed by mohit kumar 29

// JAVA program for the above approach
import java.util.*;
class GFG
{
 
// Recursive function
// to return gcd of A and B
static int GCD(int lena, int lenb)
{
  if (lena == 0)
    return lenb;
  if (lenb == 0)
    return lena;
 
  // Base case
  if (lena == lenb)
    return lena;
 
  // Length of A is greater
  if (lena > lenb)
    return GCD(lena - lenb, lenb);
  return GCD(lena, lenb - lena);
}
 
// Calculate GCD
static String StringGCD(String a, String b)
{
 
  // Store the GCD of the
  // length of the Strings
  int gcd = GCD(a.length(), b.length());
  if (a.substring(0, gcd).equals(b.substring(0, gcd)))
  {
    int x = ((int)b.length()/gcd);
    int y = ((int)a.length()/gcd);
    String r="",s="";
 
    while (x-- >0) s += a;
    while (y-- >0) r += b;
 
    if (s.equals(r))
      return a.substring(0, gcd);
  }
  return "-1";
}
 
// Driver Code
public static void main(String[] args)
{
  String a = "geeksgeeks";
  String b = "geeks";
 
  // Function call
  System.out.print(StringGCD(a, b));
}
}
 
// This code is contributed by 29AjayKumar

# Python implementation of the above approach
 
# Recursive function
# to return gcd of A and B
def GCD(lena, lenb):   
 
  if (lena == 0):
    return lenb
 
  if (lenb == 0):
    return lena
   
  # Base case
  if (lena == lenb):
    return lena
   
  # Length of A is greater
  if (lena > lenb):
    return GCD(lena-lenb, lenb)
  return GCD(lena, lenb-lena)
 
# Calculate GCD
def StringGCD(a, b):
   
  # Store the GCD of the
  # length of the strings
  gcd = GCD(len(a), len(b))
  if a[:gcd] == b[:gcd]:
 
    if a*(len(b)//gcd) == b*(len(a)//gcd):
      return a[:gcd]
 
  return -1
 
# Driver Code
a = 'geeksgeeks'
b = 'geeks'
 
# Function call
print(StringGCD(a, b))

// C# program for the above approach
using System;
class GFG
{
 
// Recursive function
// to return gcd of A and B
static int GCD(int lena, int lenb)
{
  if (lena == 0)
    return lenb;
  if (lenb == 0)
    return lena;
 
  // Base case
  if (lena == lenb)
    return lena;
 
  // Length of A is greater
  if (lena > lenb)
    return GCD(lena - lenb, lenb);
  return GCD(lena, lenb - lena);
}
 
// Calculate GCD
static String StringGCD(String a, String b)
{
 
  // Store the GCD of the
  // length of the Strings
  int gcd = GCD(a.Length, b.Length);
  if (a.Substring(0, gcd).Equals(b.Substring(0, gcd)))
  {
    int x = ((int)b.Length/gcd);
    int y = ((int)a.Length/gcd);
    String r="", s="";
 
    while (x-- >0) s += a;
    while (y-- >0) r += b;
    if (s.Equals(r))
      return a.Substring(0, gcd);
  }
  return "-1";
}
 
// Driver Code
public static void Main(String[] args)
{
  String a = "geeksgeeks";
  String b = "geeks";
 
  // Function call
  Console.Write(StringGCD(a, b));
}
}
 
// This code is contributed by 29AjayKumar

<script>
// JAVASCRIPT program for the above approach
 
// Recursive function
// to return gcd of A and B
function GCD(lena,lenb)
{
    if (lena == 0)
        return lenb;
      if (lenb == 0)
        return lena;
  
      // Base case
      if (lena == lenb)
        return lena;
  
      // Length of A is greater
      if (lena > lenb)
        return GCD(lena - lenb, lenb);
      return GCD(lena, lenb - lena);
}
 
// Calculate GCD
function StringGCD(a,b)
{
    // Store the GCD of the
      // length of the Strings
      let gcd = GCD(a.length, b.length);
      if (a.substring(0, gcd) == (b.substring(0, gcd)))
      {
        let x = Math.floor(b.length/gcd);
        let y = Math.floor(a.length/gcd);
        let r="",s="";
  
        while (x-- >0)
            s += a;
        while (y-- >0)
            r += b;
  
        if (s == (r))
              return a.substring(0, gcd);
      }
      return "-1";
}
 
// Driver Code
let a = "geeksgeeks";
let b = "geeks";
 
// Function call
document.write(StringGCD(a, b));
 
 
// This code is contributed by patel2127
</script>

geeks

Complejidad de tiempo: O(N * M), donde M es la longitud de las strings Espacio
auxiliar : O(1)