algorithm - 二进制字符串排列

Question

我在 http://www.interviewstreet.com 上遇到了一个问题.

Bob has received a binary string of length N transmitted by Alice. He knows that due to errors in transmission, up to K bits might have been corrupted (and hence flipped). However, he also knows that the string Alice had intended to transmit was not periodic. A string is not periodic if it cannot be represented as a smaller string concatenated some number of times. For example, "0001", "0110" are not periodic while "00000", "010101" are periodic strings. Now he wonders how many possible strings could Alice have transmitted.

所以首先我用二项式定理做了一些测试，通过使用它我能够找到给定一个字符串和一些损坏的位可以用多少种不同的方式来表示一个字符串。我的第二步是找到一种方法来查找周期性字符串的数量。我看到这可以很容易地用素数长度的字符串来完成。这是通过检查是否有足够的 0 或 1 来仅用 0 或 1 填充字符串来完成的。

1111111 or 0000000

现在我使用纯暴力算法，当涉及到任何类型的大字符串时，它不会削减它。是否有人可以向我指出任何一种组合数学技术可以帮助解决这个问题？谢谢。

Answer 1

Lior 走在正确的轨道上。

长度为N的字符串总数为2^N。其中一些是周期性的。其他人不是。我们称周期性字符串的数量为A(N)，非周期性字符串的数量为B(N)。然后

A(N) + B(N) = 2^N

如果我们定义长度为1的字符串是非周期的，那么

A(1) = 0
B(1) = 2

现在让我们假设 N > 1。然后，长度为 N 的周期字符串集包括周期小于 N 的周期字符串。但是，对于长度为 N 的非周期性字符串集，情况并非如此。

长度为 N 的周期字符串集由长度为 n 的约数的非周期字符串的重复组成，包括长度为 1 的字符串。换句话说:

A(N) = sum(B(k) where k divides N and k < N)

例如:

A(6) = B(1) + B(2) + B(3)
     = (2^1 - A(1)) + (2^2 - A(2)) + (2^3 - A(3))
     = 2 + (4 - B(1)) + (8 - B(1))
     = 2 + 2 + 6
     = 10

所以我们现在有一个递归方程，用于计算长度为 N 的周期性和非周期性字符串的数量。

不幸的是，这对我们回答实际问题没有多大帮助。

问题暗示 Bob 收到了一个特定的字符串，他想知道有多少个非周期性字符串与该字符串最多相差 K 位。接收到的字符串有 C(N,K) 个可能的突变，可能是传输的字符串。我们需要从中减去该集合中周期性字符串的数量。我们该怎么做？

首先，我们可以观察到任何周期性字符串都是非周期性字符串的重复。因此，对于每个可能的周期 k(N 的除数)，我们查看长度为 k 的子串。如果所有字符串与一个普通字符串的差异不超过 K 位的总和，那么这个普通字符串是周期性字符串的基础，我们应该将计数减一。如果最小距离是 d，并且 K - d > N/k，那么我们可以翻转每个子串中的各个位，并且仍然有匹配项，我们必须减少我们相应地计数。