Перестановки двоичных строк

Я столкнулся с проблемой на http://www.interviewstreet.com .

Боб получил двоичную строку длины N, переданную Алисой. Он знает, что из-за ошибок передачи до K битов могли быть повреждены (и, следовательно, перевернуты). Однако он также знает, что строка, которую Алиса намеревалась передать, не была периодической. Строка не является периодической, если она не может быть представлена ​​как меньшая строка, соединенная несколько раз. Например, «0001», «0110» не являются периодическими, а «00000», «010101» - периодическими строками. Теперь он задается вопросом, сколько возможных строк могла бы передать Алиса.

Итак, сначала я провел несколько тестов с теоремой бинома и с ее помощью я могу найти, сколько различных способов может быть представлена ​​строка с учетом строки и количества поврежденных битов. Вторым моим шагом было найти способ найти количество периодических строк. Я вижу, что это легко сделать с помощью строк с простой пронумерованной длиной. Это делается путем проверки того, достаточно ли нулей или единиц, чтобы заполнить строку только нулями или единицей.

1111111 или 0000000

Прямо сейчас я использую чистый алгоритм грубой силы, который просто не обрезает его, когда дело доходит до какой-либо большой строки. Есть ли какие-нибудь техники комбинаторики, на которые кто-нибудь мог бы указать, которые помогли бы решить эту проблему? Спасибо.