Compute binary strings of length N that are repeated concatenations of substrings

The purpose of this article is to implement a program for counting the number of binary strings of length N formed by repeated concatenation of a substring.

The goal is to determine how many binary strings of length N can be created by repeatedly concatenating individual substrings of the given text, where N is a positive integer.

Problem Statement

Implement a program for counting the number of binary strings of length N that repeatedly concatenate substrings.

Example Example 1

Let us take the Input, N = 3

Output: 2

The Chinese translation of

Explanation

is:

Explanation

Listed below are feasible binary strings of length N=3, in which a substring is repeatedly concatenated.

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

So when we count the total number of all these strings, the sum we get is 2. Therefore, the output is 2.

Example Example 2

Let us take the Input, N = 8

Output: 16

The Chinese translation of

Explanation

is:

Explanation

Listed below are feasible binary strings of length N=8, which contain repeated concatenations of substrings.

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

So when we add up the total number of all these strings, we get a sum of 16. Therefore, the output is 16.

method

In order to count the number of N-length binary strings formed by repeated concatenation of substrings, we use the following method.

A way to solve this problem and count the number of N-length binary strings that repeatedly concatenate substrings.

The above problem can be solved based on the fact that every feasible string contains a repeated substring that is concatenated C times. Therefore, the provided string length N needs to be divisible by C to generate all consecutive strings.

So first find all the divisors of N, and then for each possible divisor C, find the total number of all potential strings that can be created by concatenating them; this number can be determined using 2C. To determine the total count for each recursive call, apply the same technique to the divisor C and subtract it from 2C. This will also take into account the number of duplicate strings that exist between them.

algorithm

Algorithm for calculating a binary string of length N by repeated concatenation of the substrings given below.

• First Step − Start

• Step 2 − Define a function to count the number of strings of length N such that they are the concatenation of its substrings.

• Step 3 - Check if the status has been calculated

• Step 4 - Store the result of the current recursive call or the value of the count

• Step 5 - Iterate over all divisors

• Step 6 - Return the obtained results

• Step 7 − Stop

Example: C program

This is a C program implementation of the above algorithm, used to count the number of N-length binary strings formed by repeated concatenation of substrings.

// 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;
}

Output

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

in conclusion

Similarly, we can calculate binary strings of length N, which are repeated concatenations of substrings.

In this article the challenge of obtaining the count of an N-length binary string formed by repeated concatenation of substrings is addressed.

C programming code is provided here along with the algorithm for computing an N-length binary string that repeatedly concatenates substrings.

The above is the detailed content of Compute binary strings of length N that are repeated concatenations of substrings. For more information, please follow other related articles on the PHP Chinese website!