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

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

Матрицу смежности возводить в степень в общем виде здесь не оптимально — она сильно разрежена, ведь у каждой вершины может быть максимум 26 переходов (по числу букв в алфавите). Если просто написать динамику в лоб, должно получиться O(N^2*K*A), где N — количество состояний в автомате, К — длина слова, А — размер алфавита.