Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, Кузнец, Вы писали:
К>>Задача такова. Дан набор "запрещённых" слов, нужно подсчитать количество слов длины N, таких, что они не содержат подстрок, которые были бы среди запрещённых.
К>>Например, если запрещены строки ab, dbc, то допустимы строки типа b, ac, dba.
К>>Ограничения на размер входа таковы, что сгодится в худшем случае квадратичный алгоритм (по суммарному размеру запрещённых строк, он ограничен числом 1000).
Pzz>Очевидно, что задача решается с помощью детерминированного регулярного конечного автомата. Следовательно, время обработки входного текста можно сделать вообще не зависящим от количества запрещенных слов, и к тому же весьма быстрым (на каждый входной символ — один раз заглянуть в таблицу).
Построить по запрещённым словам автомат я могу, как после этого найти количество путей в нём, которые не задевали бы терминальные вершины, и при этом имели бы заданную длину N ?
Только что попробовал отработать такую идею. Построим матрицу переходов автомата A, выкинем из неё столбцы и строки, соответствующие терминальным состояниям, затем возведём в степень N. После чего останется просто посчитать сумму элементов A^N, находящихся в столбце корня дерева (root), это и будет число путей длины N из корня (причём не задевающих терминальных состояний, так как мы их предварительно выкинули из матрицы).
Если в автомате будет n = 2000 состояний (крайний случай, число приблизительное, но по порядку оно такое), то сложность возведения матрицы в степень будет n*n*n * log(N) (используем бинарное возведение в степень), при n = 2000 это слишком много (кубическая сложность).
