如何計算給定長度的所有可能的二進制子字符串的數量？

在下面的代碼中，我試圖計算二進制數字數組中所有可能的長度爲m的二進制子字符串，這意味着在給定的二進制數組中可以找到2^m個可能的子字符串。如何計算給定長度的所有可能的二進制子字符串的數量？

我已嘗試使用以下的方法完成任務：

byte [] E = {0,1,0,0,1,1,0,1,0,1,0,1}; 
int m=3; 
int [] c = new int [(int)Math.pow(2,m)]; 

for(int i=0;i<n;i++) 
{ 
int g=0; 
for(int j=0;j<m;j++) 
{ 
g <<= 1; 
if(E[i+j]==1) 
g++; 
} 
c[g]++; 
} 
for(int i=0;i<c.length;i++) 
System.out.print("n("+i+")->"+c[i]+"  ");

輸出：

n(0)->0  n(1)->1  n(2)->3  n(3)->1  n(4)->1  n(5)->3  n(6)->1  n(7)->0

上述方法需要2^m個存儲將被分配給數組的 'C'，這將產生OutOfMemoryError對於大數值m（比如m = 30）。

我的問題：

1.Is有沒有更好的辦法來避免這樣的錯誤，因爲m的值可能是非常大的，內存分配可能不會被允許？

2.How可以予精確測試，如果存儲器分配到該陣列實際分配之前是可能的，我已經使用

if (Runtime.getRuntime().freeMemory() < ((Integer.SIZE/8)* Math.pow(2, m))) throw new Exception("value of m too large");

檢查可用存儲器已經嘗試過，但它拋出異常時米在21和25之間，作爲實際分配發生（不使用上述測試條件）m < 25.

我的方法是否正確？

來源

2015-10-27 A. Sinha

您可以使用字典而不是數組，並且懶惰地分配條目。儘管每個條目的開銷更大，但是由於在長度爲n的字符串中僅存在長度爲m的n-m+1子字符串，因此特別是當m變大時，您將少於2個條目。因此，您可能有n-m+1條目（即使溫和m比2 ^m好得多），但只有當E具有特殊結構時，通常會少一些。

來源

2015-10-27 12:16:15 harold

在'Java'這是一個[HashMap中]（http://docs.oracle.com/javase/7/docs/api/java /util/HashMap.html） – OldCurmudgeon

這聽起來像你問張貼

如果你想從大小6（B）的陣列獲得大小3（A）的連續部分的數學不同的問題，有4子你可能得到（B - A + 1）

主陣列

BBBBBB

子陣列

AAABBB

BAAABB

BBAAAB

BBBAAA

來源

2015-10-27 12:20:44 phflack

如何計算給定長度的所有可能的二進制子字符串的數量？

回答

相關問題