Здравствуйте, Serge, Вы писали:

S>Всем привет.

S>Есть такая задача: требуется найти количество строк длины n (n <= 100), которые не содержат в себе тандемных повторов длины от 1 до k (1 <= k <= 9) над заданным алфавитом из а букв (1 <= a <= 26). Тандемным повтором называется строка вида ww, где w — это некоторая последовательность букв (в этой последовательности от 1 до k букв).

S>Будут идеи?

Решать в обратную сторону — поставить задачу сколько строк с тандемным повтором можно сделать. А дальше найти разницу.
Дело в том что количество плохих строчек оценить несколько проще:

CountRepeating(len, k) = CountNonRepeating(len, k — 2) * Z + CountNonRepeating(len, k — 4) * (Z * Z) + ...
CountNonRepeating(len, k) = Z * Z * ... Z — CountRepeating(len, k) — CountRepeating(len, k — 1) — ...

Наверное как то так, хотя вероятно нужно еще доказать достаточность такого условия.

Здравствуйте, Serge, Вы писали:

S>Всем привет.

S>Есть такая задача: требуется найти количество строк длины n (n <= 100), которые не содержат в себе тандемных повторов длины от 1 до k (1 <= k <= 9) над заданным алфавитом из а букв (1 <= a <= 26). Тандемным повтором называется строка вида ww, где w — это некоторая последовательность букв (в этой последовательности от 1 до k букв).

S>Будут идеи?

Решать в обратную сторону — поставить задачу сколько строк с подстрокой тандемным повтором можно сделать. А дальше найти разницу.
Дело в том что количество плохих строчек оценить несколько проще:

CountRepeating(len, k) = CountNonRepeating(len — 2, k — 2) * Z * (len — 2) + CountNonRepeating(len — 4, k — 4) * (Z * Z) * (len — 4) + ...
CountNonRepeating(len, k) = Z * Z * ... Z — CountRepeating(len, k) — CountRepeating(len, k — 1) — ...

Наверное как то так, хотя вероятно нужно еще доказать достаточность такого условия.

Решение выше относится к случаю когда тандемный повтор есть кусок подстроки: a0, ... ai, w0, ... wk, w0, ... wk, ai+1, ... an