фраза без повторов слов

[photon]

Пусть имеется алфавит, состоящий из $L$ букв. Любую последовательность из $W$ букв назовем словом. Последовательность из $S\geq W$ букв назовем фразой. Какова максимальная длина фразы, все слова которой различны? (слова в фразе перекрываются, то есть фраза из $S$ букв содержит $S-W+1$ слов)


Например, $ L=2$(буквы А и Б), $W=3$ (возможные варианты слов ААА, ААБ, АБА, АББ, БАА, БАБ, ББА, БББ). Максимальная фраза без повторов содержит 10 букв. Примером такой фразы будет АААБАБББАА.

А можно ли решить в общем виде для произвольных $L$, $W$ и предложить алгоритм построения фразы максимальной длины?

[Xaositect]

Собственно, $L^W + (W - 1)$, т.е. содержит все слова.
Это называется последовательности де Брёйна (de Bruijn). В статье http://en.wikipedia.org/wiki/De_Bruijn_sequence есть описание алгоритма (строится орграф, вершинами которого являются слова длины $W - 1$, а дугами соединены префикс и суффикс каждого слова длины $W$. Эйлеров цикл в таком графе будет соответствовать требуемой последовательности.)

[photon]

спасибо