Cuente el número de divisores comunes de las strings dadas

Dadas dos strings a y b , la tarea es contar el número de divisores comunes de ambas strings. Una string s es un divisor de la string t si t se puede generar repitiendo s varias veces.
Ejemplos: 
 

Entrada: a = “xaxa”, b = “xaxaxaxa” 
Salida: 2 
Los divisores comunes son “xa” y “xaxa”
Entrada: a = “bbbb”, b = “bbb” 
Salida: 1 
El único divisor común es “b ” 
 

Enfoque: para que una string s sea un candidato a divisor de la string t , se deben cumplir las siguientes condiciones: 
 

1. s debe ser un prefijo de t .
2. largo(t) % largo(s) = 0

Inicialice count = 0 y, comenzando desde el primer carácter como el carácter final del prefijo, verifique si la longitud del prefijo divide la longitud de ambas strings y también si el prefijo es el mismo en ambas strings. En caso afirmativo , actualice count = count + 1 . Repita estos pasos para todos los prefijos posibles. Imprime el valor de conteo al final.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if sub-string
// s[0...k] is repeated a number of times
// to generate string s
int check(string s, int k)
{
    for (int i = 0; i < s.length(); i++)
        if (s[i] != s[i % k])
            return false;
 
    return true;
}
 
// Function to return the count of common divisors
int countCommonDivisors(string a, string b)
{
    int ct = 0;
    int n = a.size(), m = b.size();
    for (int i = 1; i <= min(n, m); i++) {
 
        // If the length of the sub-string
        // divides length of both the strings
        if (n % i == 0 && m % i == 0)
 
            // If prefixes match in both the strings
            if (a.substr(0, i) == b.substr(0, i))
 
                // If both the strings can be generated
                // by repeating the current prefix
                if (check(a, i) && check(b, i))
                    ct++;
    }
    return ct;
}
 
// Driver code
int main()
{
    string a = "xaxa", b = "xaxaxaxa";
 
    cout << countCommonDivisors(a, b);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
    // Function that returns true if sub-string
    // s[0...k] is repeated a number of times
    // to generate String s
    static boolean check(String s, int k)
    {
        for (int i = 0; i < s.length(); i++)
        {
            if (s.charAt(i) != s.charAt(i % k))
            {
                return false;
            }
        }
        return true;
    }
 
    // Function to return the
    // count of common divisors
    static int countCommonDivisors(String a, String b)
    {
        int ct = 0;
        int n = a.length(), m = b.length();
        for (int i = 1; i <= Math.min(n, m); i++)
        {
 
            // If the length of the sub-string
            // divides length of both the strings
            if (n % i == 0 && m % i == 0) 
            {
                // If prefixes match in both the strings
                if (a.substring(0, i).equals(b.substring(0, i)))
                // by repeating the current prefix
                {
                    // If both the strings can be generated
                    if (check(a, i) && check(b, i))
                    {
                        ct++;
                    }
                }
            }
        }
        return ct;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String a = "xaxa", b = "xaxaxaxa";
        System.out.println(countCommonDivisors(a, b));
    }
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the above approach
 
# Function that returns true if sub-string
# s[0...k] is repeated a number of times
# to generate String s
def check(s, k):
 
    for i in range (0, len(s)):
     
        if (s[i] != s[i % k]):
         
            return False
         
    return True
 
# Function to return the
# count of common divisors
def countCommonDivisors(a, b):
 
    ct = 0
    n = len(a)
    m = len(b)
    for i in range(1, min(n, m) + 1):
     
        # If the length of the sub-string
        # divides length of both the strings
        if (n % i == 0 and m % i == 0):
         
            # If prefixes match in both the strings
            if (a[0 : i] == b[0 : i]) :
                 
                # by repeating the current prefix
             
                # If both the strings can be generated
                if (check(a, i) and check(b, i)) :
                 
                    ct = ct + 1
     
    return ct
     
# Driver code
a = "xaxa"
b = "xaxaxaxa"
print(countCommonDivisors(a, b))
 
# This code is contributed by ihritik

// C# implementation of the above approach
using System;
 
class GFG
{
 
// Function that returns true if sub-string
// s[0...k] is repeated a number of times
// to generate String s
static bool check(string s, int k)
{
    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] != s[i % k])
        {
            return false;
        }
    }
    return true;
}
 
// Function to return the count of
// common divisors
static int countCommonDivisors(string a,
                               string b)
{
    int ct = 0;
    int n = a.Length, m = b.Length;
    for (int i = 1;
             i <= Math.Min(n, m); i++)
    {
 
        // If the length of the sub-string
        // divides length of both the strings
        if (n % i == 0 && m % i == 0)
        {
            // If prefixes match in both the strings
            if (a.Substring(0, i) == (b.Substring(0, i)))
             
            // by repeating the current prefix
            {
                // If both the strings can be generated
                if (check(a, i) && check(b, i))
                {
                    ct++;
                }
            }
        }
    }
    return ct;
}
 
// Driver code
public static void Main()
{
    string a = "xaxa", b = "xaxaxaxa";
    Console.WriteLine(countCommonDivisors(a, b));
}
}
 
// This code is contributed by ihritik

<script>
 
// Javascript implementation of the approach
 
// Function that returns true if sub-string
// s[0...k] is repeated a number of times
// to generate string s
function check(s, k)
{
    for (var i = 0; i < s.length; i++)
        if (s[i] != s[i % k])
            return false;
 
    return true;
}
 
// Function to return the count of common divisors
function countCommonDivisors(a, b)
{
    var ct = 0;
    var n = a.length, m = b.length;
    for (var i = 1; i <= Math.min(n, m); i++) {
 
        // If the length of the sub-string
        // divides length of both the strings
        if (n % i == 0 && m % i == 0)
 
            // If prefixes match in both the strings
            if (a.substring(0, i) == b.substring(0, i))
 
                // If both the strings can be generated
                // by repeating the current prefix
                if (check(a, i) && check(b, i))
                    ct++;
    }
    return ct;
}
 
// Driver code
var a = "xaxa", b = "xaxaxaxa";
document.write( countCommonDivisors(a, b));
 
// This code is contributed by famously.
</script>

2

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)