长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量

---

本文旨在实现一个程序，用于计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量。

目标是确定，给定一个正整数 N，有多少个长度为 N 的二进制字符串可以通过重复连接给定文本的单个子串来创建。

问题陈述

实现一个程序，用于计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量。

示例 1

Let us take the Input, N = 3

Output: 2

解释

以下是长度 N=3 的可行二进制字符串，它们是由子串重复连接构成的。

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

因此，当我们计算所有这些字符串的总数时，得到的结果是 2。因此，输出为 2。

示例 2

Let us take the Input, N = 8

Output: 16

解释

以下是长度 N=8 的可行二进制字符串，它们是由子串重复连接构成的。

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

因此，当我们计算所有这些字符串的总数时，得到的结果是 16。因此，输出为 16。

方法

为了计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量，我们采用以下方法。

解决这个问题并计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量的方法。

上述问题可以基于这样一个事实来解决：每个可行字符串都包含一个重复的子串，假设重复 C 次。因此，提供的字符串长度 N 需要能够被 C 整除，才能生成所有后续的字符串。

因此，找到 N 的所有约数，然后对于每个可能的约数 C，找到可以通过连接它们创建的所有可能字符串的总数；这个数字可以使用 2^C 来确定。为了确定每个递归调用的总数，对约数 C 应用同样的方法，然后从 2^C 中减去它。这也会考虑到它们之间重复字符串的数量。

算法

以下是计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量的算法。

• 步骤 1 − 开始

• 步骤 2 − 定义一个函数来计算长度为 N 的字符串的数量，该字符串是其子串的连接。

• 步骤 3 − 检查状态是否已经被计算过。

• 步骤 4 − 存储当前递归调用的结果或计数的值。

• 步骤 5 − 遍历所有约数。

• 步骤 6 − 返回获得的结果。

• 步骤 7 − 结束

示例：C++程序

以下是上述算法的 C++ 程序实现，用于计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量。

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

结论

同样，我们可以计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量。

本文解决了获取长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量的挑战。

这里提供了 C++ 编程代码以及计算长度为 N 的二进制字符串中，由子串重复连接构成的字符串数量的算法。