計算長度為N的二進位字串，它們是子字串的重複拼接

本文的目的是實作一個程序，用於計算由一個子字串重複連接而成的長度為N的二進位字串的數量。

目標是確定透過重複連接給定文字的單一子字串，可以建立多少長度為N的二進位字串，其中N是一個正整數。

問題陳述

實作一個程序，用於計算重複連接子字串的長度為N的二進位字串的數量。

範例範例1

Let us take the Input, N = 3

Output: 2

Explanation

的中文翻譯為：

解釋

下面列出了長度為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

Explanation

的中文翻譯為：

解釋

下面列出了長度為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，發現透過連接它們可以創建的所有潛在字串的總數；這個數字可以使用2C來確定。為了確定每個遞歸呼叫的總計數，對除數C應用相同的技術，然後從2C中減去它。這也將考慮到它們之間存在的重複字串的數量。

演算法

計算下面給定的子字串重複連接的長度為N的二進位字串的演算法。

• 第一步 − 開始

• 第二步 − 定義一個函數來計算長度為N的字串的數量，使其是其子字串的連接。

• 第三步 - 檢查狀態是否已計算

• 第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長度二進位字串的演算法。

以上是計算長度為N的二進位字串，它們是子字串的重複拼接的詳細內容。更多資訊請關注PHP中文網其他相關文章！