Calculer des chaînes binaires de longueur N qui sont des concaténations répétées de sous-chaînes

Le but de cet article est d'implémenter un programme qui compte le nombre de chaînes binaires de longueur N formées par concaténation répétée d'une sous-chaîne.

L'objectif est de déterminer combien de chaînes binaires de longueur N peuvent être créées en concaténant à plusieurs reprises des sous-chaînes individuelles du texte donné, où N est un entier positif.

Énoncé du problème

Implémentez un programme qui compte le nombre de chaînes binaires de longueur N qui concatènent à plusieurs reprises des sous-chaînes.

Exemple Exemple 1

Let us take the Input, N = 3

Output: 2

La traduction chinoise de

Explication

est :

Explication

Vous trouverez ci-dessous des chaînes binaires réalisables de longueur N = 3, où une sous-chaîne est concaténée à plusieurs reprises.

"000":The substring "0" is repeatedly concatenated to form this string.
"111":The substring "1" is repeatedly concatenated to form this string.

Ainsi, lorsque nous comptons le nombre total de toutes ces chaînes, la somme que nous obtenons est de 2. La sortie est donc 2.

Exemple Exemple 2

Let us take the Input, N = 8

Output: 16

La traduction chinoise de

Explication

est :

Explication

Vous trouverez ci-dessous des chaînes binaires réalisables de longueur N = 8 contenant une concaténation répétée de sous-chaînes.

“00000000”: The substring "0" is repeatedly concatenated to form this string.
“11111111”: The substring "1" is repeatedly concatenated to form this string.
“01010101”: The substring "01" is repeatedly concatenated to form this string.
“10101010”: The substring "10" is repeatedly concatenated to form this string.
"00110011”: The substring "0011" is repeatedly concatenated to form this string.
"11001100”: The substring "1100" is repeatedly concatenated to form this string.
"11011101”: The substring "1101" is repeatedly concatenated to form this string.
"00100010”: The substring "0010" is repeatedly concatenated to form this string.
"10111011”: The substring "1011" is repeatedly concatenated to form this string.
"01000100”: The substring "0100" is repeatedly concatenated to form this string.
"10001000”: The substring "1000" is repeatedly concatenated to form this string.
"00010001”: The substring "0001" is repeatedly concatenated to form this string.
"11101110”: The substring "1110" is repeatedly concatenated to form this string.
"01110111”: The substring "0111" is repeatedly concatenated to form this string.
"01100110”: The substring "0110" is repeatedly concatenated to form this string.
"10011001”: The substring "1001" is repeatedly concatenated to form this string.

Ainsi, lorsque nous additionnons le nombre total de toutes ces chaînes, nous obtenons une somme de 16. La sortie est donc 16.

Méthode

Pour compter le nombre de chaînes binaires de longueur N formées par concaténation répétée de sous-chaînes, nous utilisons la méthode suivante.

Un moyen de résoudre ce problème et de compter le nombre de chaînes binaires de longueur N en concaténant à plusieurs reprises des sous-chaînes.

Le problème ci-dessus peut être résolu sur la base du fait que chaque chaîne réalisable contient une sous-chaîne répétée qui est concaténée C fois. Par conséquent, la longueur de chaîne fournie N doit être divisible par C pour générer toutes les chaînes consécutives.

Donc, trouvez d'abord tous les diviseurs de N, puis pour chaque diviseur possible C, trouvez le nombre total de toutes les chaînes potentielles qui peuvent être créées en les concaténant, ce nombre peut être déterminé en utilisant 2C ; Pour déterminer le nombre total de chaque appel récursif, appliquez la même technique au diviseur C et soustrayez-le de 2C. Cela prendra également en compte le nombre de chaînes en double présentes entre elles.

Algorithme

Algorithme de calcul d'une chaîne binaire de longueur N par concaténation répétée de sous-chaînes donné ci-dessous.

• Première étape − Démarrer

• Étape 2 - Définissez une fonction pour compter le nombre de chaînes de longueur N telles qu'elles soient la concaténation de ses sous-chaînes.

• Étape 3 - Vérifiez si le statut a été calculé

• Étape 4 - Stocker le résultat de l'appel récursif en cours ou la valeur du décompte

• Étape 5 - Itérer sur tous les diviseurs

• Étape 6 - Renvoyez les résultats obtenus

• Étape 7 − Arrêtez

Exemple : programme C++

Il s'agit d'une implémentation de programme C de l'algorithme ci-dessus pour compter le nombre de chaînes binaires de longueur N formées par concaténation répétée de sous-chaînes.

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;

// Storing all the states of recurring recursive 
map<int, int> dp;

// Function for counting the number of strings of length n wherein thatstring is a  concatenation of its substrings
int countTheStrings(int n){

   //the single character cannot be repeated
   if (n == 1)
      return 0;
      
   // Checking whether the state is calculated already or not
   if (dp.find(n) != dp.end())
      return dp[n];
      
      // Storing those value of the result or the count for the present recursive call
   int res = 0;
   
   // Iterate through all of the divisors
   for(int d= 1; d <= sqrt(n); d++){
      if (n % d== 0){
         res += (1 << d) -  countTheStrings(d);
         int div1 = n/d;
         if (div1 != d and d!= 1)
         
            // Non-Rep = Total - Rep
            res += (1 << div1) -  countTheStrings(div1);
      }
   }
   
   // Storing the result of the above calculations
   dp[n] = res; 
   
   // Returning the obtained result
   return res;
}
int main(){
   int n = 8;
   cout<< "Count of 8-length binary strings that are repeated concatenation of a substring: "<< endl;
   cout << countTheStrings(n) << endl;
}

Sortie

Count of 8-length binary strings that are repeated concatenation of a substring −
16

Conclusion

De même, nous pouvons calculer des chaînes binaires de longueur N, qui sont des concaténations répétées de sous-chaînes.

Dans cet article, le défi consistant à obtenir le décompte d'une chaîne binaire de longueur N formée par concaténation répétée de sous-chaînes est abordé.

Le code de programmation C++ est fourni ici avec l'algorithme de calcul de chaînes binaires de longueur N de sous-chaînes concaténées à plusieurs reprises.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!