Здравствуйте, Кузнец, Вы писали:

Pzz>>Очевидно, что задача решается с помощью детерминированного регулярного конечного автомата. Следовательно, время обработки входного текста можно сделать вообще не зависящим от количества запрещенных слов, и к тому же весьма быстрым (на каждый входной символ — один раз заглянуть в таблицу).

К>Построить по запрещённым словам автомат я могу, как после этого найти количество путей в нём, которые не задевали бы терминальные вершины, и при этом имели бы заданную длину N ?

Я наконец осознал, что надо не фильтровать строки на хорошие/плохие на лету, а подсчитать количество хороших строк заданной длинны.

А зачем может понадобиться такое странное число?

Заметим, что задача была бы тривиальной, если бы автомат представлялся ациклическим графом. Проблема именно с циклами. Надо подумать, как наличие цикла влияет на ответ.