Número de strings base común para dos strings

Dadas dos strings s1 y s2, necesitamos encontrar un número de strings base común de dos. Una substring de una string s se denomina string base si la concatenación repetida de la substring da como resultado s.
Ejemplos: 
 

Input : s1 = "pqrspqrs"
        s2 = "pqrspqrspqrspqrs"
Output : 2
The two common base strings are "pqrs"
and "pqrspqrs".

Input: s1 = "bbb"
       s2 = "bb"
Output: 1
There is only one common base string
which is "b". 

La longitud máxima posible de la string base común es igual a la longitud de la menor de dos strings. Así que ejecutamos un ciclo que considera todos los prefijos de string más pequeña y para cada prefijo verifica si es una base común.
A continuación se muestra la implementación del siguiente enfoque. 
 

// CPP program to count common base strings
// of s1 and s2.
#include <bits/stdc++.h>
using namespace std;
 
// function for finding common divisor .
bool isCommonBase(string base, string s1, 
                               string s2)
{
    // Checking if 'base' is base string 
    // of 's1'
    for (int j = 0; j < s1.length(); ++j)
        if (base[j % base.length()] != s1[j])
            return false;
     
    // Checking if 'base' is base string
    // of 's2'
    for (int j = 0; j < s2.length(); ++j)
        if (base[j % base.length()] != s2[j])
            return false;   
 
    return true;
}
 
int countCommonBases(string s1, string s2) {
   int n1 = s1.length(), n2 = s2.length();
   int count = 0;
   for (int i=1; i<=min(n1, n2); i++)
   {
       string base = s1.substr(0, i);
       if (isCommonBase(base, s1, s2))
           count++;
   }
   return count;
}
 
// Driver code
int main()
{
    string s1 = "pqrspqrs";
    string s2 = "pqrspqrspqrspqrs";
    cout << countCommonBases(s1, s2) << endl;
    return 0;
}

// Java program to count common
// base strings of s1 and s2.
 
class GFG
{
 
// function for finding common divisor
static boolean isCommonBase(String base,
                            String s1,
                            String s2)
{
    // Checking if 'base' is base
    // String of 's1'
    for (int j = 0; j < s1.length(); ++j)
    {
        if (base.charAt(j %
            base.length()) != s1.charAt(j))
        {
            return false;
        }
    }
 
    // Checking if 'base' is base
    // String of 's2'
    for (int j = 0; j < s2.length(); ++j)
    {
        if (base.charAt(j %
            base.length()) != s2.charAt(j))
        {
            return false;
        }
    }
 
    return true;
}
 
static int countCommonBases(String s1,
                            String s2)
{
    int n1 = s1.length(),
        n2 = s2.length();
    int count = 0;
    for (int i = 1; i <= Math.min(n1, n2); i++)
    {
        String base = s1.substring(0, i);
        if (isCommonBase(base, s1, s2))
        {
            count++;
        }
    }
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    String s1 = "pqrspqrs";
    String s2 = "pqrspqrspqrspqrs";
 
    System.out.println(countCommonBases(s1, s2));
}
}
 
// This code is contributed by Rajput-JI

# Python 3 program to count common
# base strings of s1 and s2.
 
# function for finding common divisor .
def isCommonBase(base, s1, s2):
 
    # Checking if 'base' is base
    # string of 's1'
    for j in range(len(s1)):
        if (base[j % len(base)] != s1[j]):
            return False
     
    # Checking if 'base' is base
    # string of 's2'
    for j in range(len(s2)):
        if (base[j % len( base)] != s2[j]):
            return False
 
    return True
 
def countCommonBases(s1, s2):
    n1 = len(s1)
    n2 = len(s2)
    count = 0
    for i in range(1, min(n1, n2) + 1):
        base = s1[0: i]
        if (isCommonBase(base, s1, s2)):
            count += 1
         
    return count
 
# Driver code
if __name__ == "__main__":
     
    s1 = "pqrspqrs"
    s2 = "pqrspqrspqrspqrs"
    print(countCommonBases(s1, s2))
 
# This code is contributed by ita_c

// C# program to count common base
// strings of s1 and s2.
using System;
 
class GFG
{
// function for finding common divisor
static bool isCommonBase(String Base,
                         String s1,
                         String s2)
{
    // Checking if 'base' is base
    // String of 's1'
    for (int j = 0; j < s1.Length; ++j)
    {
        if (Base[j % Base.Length] != s1[j])
        {
            return false;
        }
    }
 
    // Checking if 'base' is base
    // String of 's2'
    for (int j = 0; j < s2.Length; ++j)
    {
        if (Base[j % Base.Length] != s2[j])
        {
            return false;
        }
    }
 
    return true;
}
 
static int countCommonBases(String s1,
                            String s2)
{
    int n1 = s1.Length, n2 = s2.Length;
    int count = 0;
    for (int i = 1;
             i <= Math.Min(n1, n2); i++)
    {
        String Base = s1.Substring(0, i);
        if (isCommonBase(Base, s1, s2))
        {
            count++;
        }
    }
    return count;
}
 
// Driver code
public static void Main()
{
    String s1 = "pqrspqrs";
    String s2 = "pqrspqrspqrspqrs";
 
    Console.Write(countCommonBases(s1, s2));
}
}
 
// This code is contributed by Rajput-JI

<?php
// PHP program to count common base strings
// of s1 and s2.
 
// function for finding common divisor .
function isCommonBase($base,$s1, $s2)
{
    // Checking if 'base' is base string
    // of 's1'
    for ($j = 0; $j < strlen($s1); ++$j)
        if ($base[$j % strlen($base)] != $s1[$j])
            return false;
     
    // Checking if 'base' is base string
    // of 's2'
    for ($j = 0; $j < strlen($s2); ++$j)
        if ($base[$j % strlen($base)] != $s2[$j])
            return false;
 
    return true;
}
 
function countCommonBases($s1, $s2)
{
    $n1 = strlen($s1);
    $n2 = strlen($s2);
    $count = 0;
    for ($i = 1; $i <= min($n1, $n2); $i++)
    {
        $base = substr($s1,0, $i);
        if (isCommonBase($base, $s1, $s2))
            $count++;
    }
    return $count;
}
 
// Driver code
    $s1 = "pqrspqrs";
    $s2 = "pqrspqrspqrspqrs";
    echo countCommonBases($s1, $s2)."\n";
 
// This code is contributed by mits
?>

<script>
// Javascript program to count common
// base strings of s1 and s2.
     
    // function for finding common divisor
    function isCommonBase(base,s1,s2)
    {
     
        // Checking if 'base' is base
    // String of 's1'
    for (let j = 0; j < s1.length; ++j)
    {
        if (base[j % base.length] != s1[j])
        {
            return false;
        }
    }
   
    // Checking if 'base' is base
    // String of 's2'
    for (let j = 0; j < s2.length; ++j)
    {
        if (base[j %base.length] != s2[j])
        {
            return false;
        }
    }
   
    return true;
    }
     
    function countCommonBases(s1,s2)
    {
        let n1 = s1.length,
        n2 = s2.length;
    let count = 0;
    for (let i = 1; i <= Math.min(n1, n2); i++)
    {
        let base = s1.substring(0, i);
        if (isCommonBase(base, s1, s2))
        {
            count++;
        }
    }
    return count;
    }
     
    // Driver code
    let s1 = "pqrspqrs";
    let s2 = "pqrspqrspqrspqrs";
    document.write(countCommonBases(s1, s2));
             
    // This code is contributed by rag2127
</script>

2

Complejidad del tiempo: O(min(n1, n2) * (n1 + n2))