c - 如何计算没有。包含子字符串“00”的二进制字符串？

Question

我需要计算没有包含“00”作为子字符串的可能子字符串。我知道二进制字符串的长度。

例如：对于长度为 4 的字符串，可能的子字符串为：0000 0001 0010 0011 0100 1000 1001 1100

我只需要可能组合的数量，而不是枚举所有组合

PS：最大长度 10^6

Answer 1

这是使用斐波那契 n 步数序列计算的。

长度为 n 的字符串中包含 k 个 0 的字符串排列数为 2^n-fibk( n + 2 )。

在您的情况下，您有 k = 2，因此您使用正常的斐波那契序列为您的示例提供解决方案，字符串长度为 n = 4：2^4 - fib( 6 )= 16 - 8 = 8。

编辑：见这里： http: //mathworld.wolfram.com/Fibonaccin-StepNumber.html

Answer 2

我想我可以给你一个算法的想法：

让count(n)为字符串 o 长度的包含“00”的可能子字符串的数量n。

s(n)我们现在检查大小为n(n > 3)的字符串。假设c[i]它是数字（1 <= i <= n）和s(j)第一个j数字的子字符串（i <= j < n）。

1. 如果s(n-1)已经包含“00”则s(n)也包含“00”，无论c[n]是“0”还是“1”。所以我们已经有了2 * count(n-1)匹配条件的字符串。
2. 如果s(n-1)不包含“00”，但包含s(n)，则s(n-1)必须以“0”结尾（因此c[n-1]必须为“0”）并且c[n]必须为“0”。因为c[n-1] = "0",c[n-2] 必须是“1”（否则s(n-1)会以“00”结尾）。所以我们知道它s(n-1)以“10”结尾。s(n-3)（“10”之前的子字符串！）可以是任何不包含“00”的字符串，并且有2^(n-3) - count(n-3)。

两者相加，我们得到count(n) = 2*count(n-1) + 2^(n-3) - count(n-3)

我们知道count(1) = 0（因为字符串太短），count(2) = 1 (00) 和count(3) = 3 (000, 001, 100)。所以我们可以开始一个迭代，让我们尝试 n=4 （你已经有了结果）：

count(4) = 2*count(3) +2^1 - count(1) = 2*3 + 2 - 0 = 8