我在http://www.interviewstreet.com上遇到了一个问题.
Bob收到了Alice发送的长度为N的二进制字符串.他知道由于传输错误,最多K位可能已被破坏(因此被翻转).但是,他也知道Alice打算传输的字符串不是周期性的.如果字符串不能表示为连接多次的较小字符串,则该字符串不是周期性的.例如,"0001","0110"不是周期性的,而"00000","010101"是周期性字符串.现在他想知道Alice有多少可能的字符串传输.
首先,我使用二项式定理进行了一些测试,并通过使用它,我能够找到在给定字符串和多个损坏位的情况下可以表示字符串的不同方式.我的第二步是找到一种方法来查找周期性字符串的数量.我看到这可以通过带有素数长度的字符串轻松完成.这是通过检查是否有足够的0或1来填充字符串仅用0或1来完成.
1111111或0000000
现在我使用的是一种纯粹的强力算法,当涉及到任何类型的大字符串时,它都不会削减它.是否有任何类型的组合技术可以指出我有助于解决这个问题？谢谢.