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

Question

问题是找到长度为nA的二进制字符串的可重复二进制字符串的数量是可重复的,如果它可以通过重复自身以形成原始二进制字符串的二进制字符串的任何子字符串来获得.

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 = 40的小n也是不可行的.

我认为的第二种方法是

1. 对于n的除数k,找到长度为k的所有子串,其重复自身n/k次

n = 6的例子我们有除数1,2,3

对于长度为1,我们有2子串"1"和"0"自身重复6次,从而"111111"和"000000"是可重复的串

对于长度2,我们有4个子字符串"00""01""10""11"所以"000000""010101""101010"和"111111"是可重复的字符串

类似于长度3,我们有8个可重复的字符串.

2. 总结所有除数生成的字符串并减去重复项.

在上面的例子中,每个除数的字符串"111111"和"000000"被计算了3次.显然我在计数.我需要减去重复但是我无法想到从我的实际数量中减去重复数量我怎样才能做到这一点？

我是朝着正确的方向前进还是需要采取其他方法？

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, ...对所有分隔符继续此操作。