统计长度为 n 的可重复二进制字符串数量

Question

问题是找到长度为n的可重复二进制字符串的数量。如果一个二进制字符串可以通过任何重复自身以形成原始二进制字符串的子字符串来获得，则该二进制字符串是可重复的。

Example
"1010" is a repeatable string as it can be obtained from "10" by repeating 2 number of times

"1001" is  not a repeatable string as it cannot be obtained from any sub string of "1001" by repeating them any number of times

我想到的解决方案是生成所有长度为n的可能二进制字符串，并使用KMP算法检查它是否可重复，但即使对于小值n（如n = 40），这种解决方案也不可行。

我考虑的第二种方法是： 1. 对于n的除数k，找到长度为k的所有子串，重复出现n/k次。 例如当n=6时，我们有除数1、2、3。对于长度为1，我们有两个子串“1”和“0”，它们分别重复出现6次，因此“111111”和“000000”是可重复的字符串；对于长度为2，我们有4个子串“00”、“01”、“10”、“11”，因此“000000”、“010101”、“101010”和“111111”是可重复的字符串；类似地，对于长度为3，有8个可重复的字符串。 2. 总结所有生成的字符串并减去重复项。

在上面的例子中，“111111”和“000000”每个除数都被计算了3次，所以很明显我计算的数量过多。我需要减去重复项，但我无法想到从实际计数中减去重复项的任何方法。我是否朝着正确的方向前进？还是需要其他方法？

- Prashant Bhanarkar

---

您当前的方法看起来不错。要想弄清楚如何避免重复计算字符串，最好查看（例如维基百科上的）容斥原理文章。 - j_random_hacker

Answer 1

当您使用第二种方案时，请删除由可重复的二进制组成的子字符串。例如，00和11分别由0和1的重复组成。因此，对于长度为2，只考虑“01”和“10” 对于长度为3，只考虑“001”，“010”，“011”，“100”，“101”，“110” ... 一般来说， 对于奇数长度的n，删除0和（2 ^ n）-1， 对于偶数长度的n，删除0，（2 ^（n / 2）+1），（2 ^（n / 2）+1） 2，....，（2 ^ n）-1 如果n可被3整除，则删除（1 + 2 ^（n / 2）+2 ^（n-2）），（1 + 2 ^（n / 2）+2 ^（n-2）） 2，... 对所有除数继续执行此操作。

- Hoda

Answer 2

一种想法是，如果我们只计算由非重复子字符串制作出除数大小的字符串的方法，那么除数的除数的计数将包含由重复子字符串制作出除数的方法。

f(1) = 0
f(n) = sum(2^d - f(d)), where 1 <= d < n and d divides n

...意味着只有n的因数可以由非重复子串组成的方式的总和。

f(2) = 2^1-0
f(3) = 2^1-0
f(4) = 2^1-0 + 2^2-2
f(6) = 2^1-0 + 2^2-2 + 2^3-2
...

- גלעד ברקן