Таки нашел

В далеком-далеком 2002 (а может и 2003?) году, когда я был на первом (а может и втором) курсе, на 1/4 финале в Челябинске была задача.

Задача. Есть кодовый замок, с конечным алфавитом (мощность n), который проверяет пароли длины m. Если вы подаете более длинную строку, то замок проверяет методом "скользящего окна", то есть откусываю одну букву слева от входа, и подавая следующую на вход.

Задача - сгенерить строку, минимальную по длине, которая перебирает все пароли.

Мы тогда, естественно, не решили. На тот момент у нас был никакой уровень (точнее, уровня не было вообще). Решило задачу команды 1-2. На разборе было как-то вообще смято. Демидов сказал что-то боянистое "те кто решили - решили, а кто не решил - тот не решил". Единственное, что он сказал что есть какой-то "алгоритм змейки"...

И вот, я все это время думал что тут реально что-то сложное. Ибо гуглил, и ничего про "змейку" не находил.

На днях наткнутлся на последовательность ДеБрёйна (http://en.wikipedia.org/wiki/De_Bruijn_sequence). Один в один, то что надо. Его именем, правда, много чего есть, и та же классика для графа при секвенировании генома. Тут почти тот же граф.

Очевидным образом все сводится к Эйлерову графу, тупо линия. (Взять все слова. Ребро есть, если откусить и приписать один символ). Сейчас это выглядит халявой. Да, там есть магия, чтобы обойтись без графа вообще, но надо несильно покурить.

Причем, я раза 2-3 спрашивал у Паши про эту задачу. Видимо, ему было немного лень подумать. У меня возникает стойкое ощущение, что в данном случае моя лень больше. А может это не лень? Что гораздо хуже. Проблема, что нашел, а не додумался до вроде бы очевидных вещей, вот тут несколько обидно.

Одиннадцать лет назад я многое не знал.

ЗЫ. Увы, сейчас я не знаю еще больше.

ЗЗЫ. То, что я знаю несколько больше, совсем не считается в свете предыдущего утверждения.