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

К>Задача такова. Дан набор "запрещённых" слов, нужно подсчитать количество слов длины N, таких, что они не содержат подстрок, которые были бы среди запрещённых.

К>Например, если запрещены строки ab, dbc, то допустимы строки типа b, ac, dba.

К>Ограничения на размер входа таковы, что сгодится в худшем случае квадратичный алгоритм (по суммарному размеру запрещённых строк, он ограничен числом 1000).

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