Home > Article > Backend Development > 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.
Implement a program for counting the number of binary strings of length N that repeatedly concatenate substrings.
Let us take the Input, N = 3
Output: 2The Chinese translation of
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.
Let us take the Input, N = 8
Output: 16The Chinese translation of
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.
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 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
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; }
Count of 8-length binary strings that are repeated concatenation of a substring − 16
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!