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

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

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

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

Это учебная задача по программированию на применение автоматов.

Если бы автомат был без циклов, то да, удалили все терминальные состояния и посчитали, сколько осталось состояний ) Если есть циклы (они же, откаты), то всё хитрее, но не сильно. Нужно посчитать количество путей заданной длины в графе, которые выходят из корня и не проходят по терминалам (запрещённые вершины, её посещение означает, что в нашей строке нашлась запрещённая подстрока). Удалим из графа все запрещённые вершины, а полученный граф будем анализировать с точки зрения числа путей. Тут я и применил алгоритм с матрицей — матрицу смежности возводим в нужную степень и считаем у неё сумму элементов столбца, соответствующего вершине root, это и будет ответом. Матрицу можно возвести в степень за O(n^3 * log(k)) — бинарным алгоритмом, выше был предложен более быстрый алгоритм за O(n^{2.8} * log(k)) (с показателем мог чуть ошибиться, он точно меньше 3), но это всё равно слишком долго, крайние случаи n = 2000 и k = 1000. Тут только квадратичный алгоритм (скорее всего)...