Рубрики

Количество общих базовых строк для двух строк

Учитывая две строки s1 и s2, нам нужно найти количество общих базовых строк, равное двум. Подстрока строки s называется базовой строкой, если многократная конкатенация подстроки приводит к s.

Примеры:

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". 

Максимально возможная длина общей базовой строки равна длине меньшей из двух строк. Таким образом, мы запускаем цикл, который учитывает все префиксы строки меньшего размера и для каждого префикса проверяет, является ли она общей базой.

Ниже приведена реализация следующего подхода

C ++

// Программа CPP для подсчета общих базовых строк
// из s1 и s2.
#include <bits/stdc++.h>

using namespace std;

  
// функция для нахождения общего делителя.

bool isCommonBase(string base, string s1,  

                               string s2)

{

    // Проверка, является ли 'base' базовой строкой

    // из 's1'

    for (int j = 0; j < s1.length(); ++j) 

        if (base[j % base.length()] != s1[j])

            return false;

      

    // Проверка, является ли 'base' базовой строкой

    // из '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;

}

  
// Код драйвера

int main()

{

    string s1 = "pqrspqrs";

    string s2 = "pqrspqrspqrspqrs";

    cout << countCommonBases(s1, s2) << endl;

    return 0;

}

Джава

// Java-программа для подсчета общего
// базовые строки s1 и s2.

  

class GFG 

{

  
// функция для нахождения общего делителя

static boolean isCommonBase(String base, 

                            String s1, 

                            String s2)

{

    // Проверка, является ли base

    // Строка 's1'

    for (int j = 0; j < s1.length(); ++j) 

    {

        if (base.charAt(j % 

            base.length()) != s1.charAt(j))

        {

            return false;

        }

    }

  

    // Проверка, является ли base

    // Строка '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;

}

  
// Код драйвера

public static void main(String[] args)

{

    String s1 = "pqrspqrs";

    String s2 = "pqrspqrspqrspqrs";

  

    System.out.println(countCommonBases(s1, s2));

}
}

  
// Этот код предоставлен Rajput-JI

Python 3

# Python 3 программа для подсчета общего
# базовые строки s1 и s2.

  
# функция для нахождения общего делителя.

def isCommonBase(base, s1, s2):

  

    # Проверка, является ли «база» базовой

    # строка 's1'

    for j in range(len(s1)): 

        if (base[j % len(base)] != s1[j]):

            return False

      

    # Проверка, является ли «база» базовой

    # строка '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

  
# Код драйвера

if __name__ == "__main__":

      

    s1 = "pqrspqrs"

    s2 = "pqrspqrspqrspqrs"

    print(countCommonBases(s1, s2))

  
# Этот код предоставлен ita_c

C #

// C # программа для подсчета общей базы
// строки s1 и s2.

using System;

  

class GFG


// функция для нахождения общего делителя

static bool isCommonBase(String Base, 

                         String s1, 

                         String s2) 

{

    // Проверка, является ли base

    // Строка 's1'

    for (int j = 0; j < s1.Length; ++j) 

    {

        if (Base[j % Base.Length] != s1[j]) 

        {

            return false;

        }

    }

  

    // Проверка, является ли base

    // Строка '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;

}

  
// Код драйвера

public static void Main() 

{

    String s1 = "pqrspqrs";

    String s2 = "pqrspqrspqrspqrs";

  

    Console.Write(countCommonBases(s1, s2));

}
}

  
// Этот код предоставлен Rajput-JI

PHP

<?php
// PHP-программа для подсчета общих базовых строк
// из s1 и s2.

  
// функция для нахождения общего делителя.

function isCommonBase($base,$s1, $s2)

{

    // Проверка, является ли 'base' базовой строкой

    // из 's1'

    for ($j = 0; $j < strlen($s1); ++$j

        if ($base[$j % strlen($base)] != $s1[$j])

            return false;

      

    // Проверка, является ли 'base' базовой строкой

    // из '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;

}

  
// Код драйвера

    $s1 = "pqrspqrs";

    $s2 = "pqrspqrspqrspqrs";

    echo countCommonBases($s1, $s2)."\n";

  
// Этот код предоставлен mits
?>

Выход:

2

Сложность времени: O (мин (n1, n2) * (n1 + n2))

Рекомендуемые посты:

Количество общих базовых строк для двух строк

0.00 (0%) 0 votes