如何计算给定长度的所有可能的二进制子字符串的数量？

在下面的代码中，我试图计算二进制数字数组中所有可能的长度为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

如何计算给定长度的所有可能的二进制子字符串的数量？

回答

相关问题