Задача такова. Дан набор "запрещённых" слов, нужно подсчитать количество слов длины N, таких, что они не содержат подстрок, которые были бы среди запрещённых.
Например, если запрещены строки ab, dbc, то допустимы строки типа b, ac, dba.
Ограничения на размер входа таковы, что сгодится в худшем случае квадратичный алгоритм (по суммарному размеру запрещённых строк, он ограничен числом 1000).
Что в настоящий момент удалось понять.
Можно по данному набору слов построить автомат Ахо-Корасик (он же бор с суффиксными и терминальными ссылками), затем запустить по автомату следующую динамику.
Пусть v — состояние автомата, n — число, положим f(v, n) — количество строк длины n, которые можно прочитать из состояния v и при этом в процессе чтения не попадать в терминальные вершины. Тогда ответом в задаче будет f(root, N) — число слов длины N, которые можно прочитать из корня автомата, при этом не попав ни разу в терминальную вершину (попадание в терминальную вершину означает нахождение запрещённой подстроки, помним, что у нас автомат построен по запрещённым подстрокам).
Формула динамики имеет простой вид:
f(v, n) = сумма f(g(v, sym), n — 1)
сумма ведётся по всем символам c, здесь через g(v, c) обозначено состояние, в которое мы попадём, пойдя из состояния v по символу sym. Граничные условия:
f(v, n) = 0, если v — терминальное, f(v, 0) = 1.
Эта динамика с такими условиями полностью описывает задачу и даёт верный ответ. Но она слишком долгая. Время её работы по порядку превосходит ответ, а ответ здесь может быть огромным (например, если допустима длина 10, а символов 26 — все буквы английского алфавита, при этом запрещённых слов нет, то ответ будет 10^26, и мы будем его собирать по единичке, затратив на всё дело слишком много времени).
Данное решения взял из гугла с форума алголиста. Что-то идей, как это можно улучшить, нету (.
Этот алгоритм можно как-то ускорить ? И если нет, то подкиньте хотя бы идею, как эту задачу можно решить...
Здравствуйте, Кузнец, Вы писали:
К>Эта динамика с такими условиями полностью описывает задачу и даёт верный ответ. Но она слишком долгая. Время её работы по порядку превосходит ответ, а ответ здесь может быть огромным (например, если допустима длина 10, а символов 26 — все буквы английского алфавита, при этом запрещённых слов нет, то ответ будет 10^26, и мы будем его собирать по единичке, затратив на всё дело слишком много времени).
По единичке? Нет, конечно. Гораздо быстрее.
С такими условиями во всём автомате будет одна вершина с 26-ю петлями. То есть один переход от (n-1) к (n) требует 26 сложений чисел. Всего таких переходов будет 10 для длины 10. Итого, потребуется 260 сложений чисел. Ответ, кстати говоря, будет не 10^26, а 26^10, то есть для его подсчёта даже длинной арифметики не надо.
Честно говоря, 260 сложений 64-битных чесел — это не так уж и много. Странно, что у тебя это тормозит :)
Но вот ещё совет: можно объединять одинаковые переходы в одно ребро, сохраняя его кратность (ведь при подсчёте не важно по какому символу произошел переход, а это единственное отличие рёбер между зафиксированной парой вершин). Тогда можно разменять сложения на умножения — иногда это выгодно. Так в этом примере для вычисления понадобится сделать всего 10 сложений и 10 умножений 64-битных чисел — вряд-ли что-то быстрее можно найти.
Короче говоря, если это тормозит, то предсказываю, что где-то лажа с реализацией, а не с алгоритмом.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, Кузнец, Вы писали:
К>>Эта динамика с такими условиями полностью описывает задачу и даёт верный ответ. Но она слишком долгая. Время её работы по порядку превосходит ответ, а ответ здесь может быть огромным (например, если допустима длина 10, а символов 26 — все буквы английского алфавита, при этом запрещённых слов нет, то ответ будет 10^26, и мы будем его собирать по единичке, затратив на всё дело слишком много времени).
W>По единичке? Нет, конечно. Гораздо быстрее. W>С такими условиями во всём автомате будет одна вершина с 26-ю петлями. То есть один переход от (n-1) к (n) требует 26 сложений чисел. Всего таких переходов будет 10 для длины 10. Итого, потребуется 260 сложений чисел. Ответ, кстати говоря, будет не 10^26, а 26^10, то есть для его подсчёта даже длинной арифметики не надо. W>Честно говоря, 260 сложений 64-битных чесел — это не так уж и много. Странно, что у тебя это тормозит W>Но вот ещё совет: можно объединять одинаковые переходы в одно ребро, сохраняя его кратность (ведь при подсчёте не важно по какому символу произошел переход, а это единственное отличие рёбер между зафиксированной парой вершин). Тогда можно разменять сложения на умножения — иногда это выгодно. Так в этом примере для вычисления понадобится сделать всего 10 сложений и 10 умножений 64-битных чисел — вряд-ли что-то быстрее можно найти.
W>Короче говоря, если это тормозит, то предсказываю, что где-то лажа с реализацией, а не с алгоритмом.
Дно рекурсии — единица, ответ программа разлагает на сумму нулей и единиц и их суммирует, так что алгоритм время ест )
Здравствуйте, Кузнец, Вы писали:
К>>>например, если допустима длина 10, а символов 26 — все буквы английского алфавита, при этом запрещённых слов нет, то ответ будет 10^26, и мы будем его собирать по единичке, затратив на всё дело слишком много времени.
К>Дно рекурсии — единица, ответ программа разлагает на сумму нулей и единиц и их суммирует, так что алгоритм время ест )
Сколько сложений делает твоя реализация на этом примере? Алгоритму, описанному в твоём же первом сообщении, достаточно 260 сложений. Если твоя реализация делает больше — то значит реализация плохая. Нужно её выкинуть и воплотить в код ровно то, что описано текстом в твоём первом сообщении. Только потом к этому имеет смысл добавлять сжатие путей и прочие оптимизации.
Здравствуйте, Кузнец, Вы писали:
К>Задача такова. Дан набор "запрещённых" слов, нужно подсчитать количество слов длины N, таких, что они не содержат подстрок, которые были бы среди запрещённых.
К>Например, если запрещены строки ab, dbc, то допустимы строки типа b, ac, dba.
К>Ограничения на размер входа таковы, что сгодится в худшем случае квадратичный алгоритм (по суммарному размеру запрещённых строк, он ограничен числом 1000).
Очевидно, что задача решается с помощью детерминированного регулярного конечного автомата. Следовательно, время обработки входного текста можно сделать вообще не зависящим от количества запрещенных слов, и к тому же весьма быстрым (на каждый входной символ — один раз заглянуть в таблицу).
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, Кузнец, Вы писали:
К>>>>например, если допустима длина 10, а символов 26 — все буквы английского алфавита, при этом запрещённых слов нет, то ответ будет 10^26, и мы будем его собирать по единичке, затратив на всё дело слишком много времени.
К>>Дно рекурсии — единица, ответ программа разлагает на сумму нулей и единиц и их суммирует, так что алгоритм время ест )
W>Сколько сложений делает твоя реализация на этом примере? Алгоритму, описанному в твоём же первом сообщении, достаточно 260 сложений. Если твоя реализация делает больше — то значит реализация плохая. Нужно её выкинуть и воплотить в код ровно то, что описано текстом в твоём первом сообщении. Только потом к этому имеет смысл добавлять сжатие путей и прочие оптимизации.
Либо 260 сложений этому алгоритму недостаточно, либо я его попросту неверно понял. Описанный алгоритм разлагает ответ в сумму единиц и их складывает, по-моему это в первом сообщении и описано (идёт рекурсия функцией f, рекурсивный вызов обрывается лишь если второй аргумент f равен нулю, при такой ситуации значение f будет равно 1, то есть внизу рекурсии у нас только единицы).
Моя реализация ровно это и делает. Если я неверно понял алгоритм, и всё же в каких-то случаях внизу рекурсии окажутся не единицы — прошу помочь разобраться, как именно должен выглядеть алгоритм.
Здравствуйте, 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 это слишком много (кубическая сложность).
Здравствуйте, Кузнец, Вы писали:
К>Либо 260 сложений этому алгоритму недостаточно, либо я его попросту неверно понял. Описанный алгоритм разлагает ответ в сумму единиц и их складывает, по-моему это в первом сообщении и описано (идёт рекурсия функцией f, рекурсивный вызов обрывается лишь если второй аргумент f равен нулю, при такой ситуации значение f будет равно 1, то есть внизу рекурсии у нас только единицы).
Это сейчас у тебя рекурсия написана, а в первом сообщении написано про динамику. В динамическом программировании не нужно повторно решать уже решенные задачи. Спуск до единиц произойдёт только при первом переходе от длины 0 к длине 1. Больше они никогда в решении не возникнут.
К> как именно должен выглядеть алгоритм.
Алгоритм — как написано. Простейшая реализация — так:
Пусть V - число состояний автомата
завести два массива A[V] и B[V]
инициализировать массив A значениями 0 или 1 в зависимости от того, является ли соответствующее состояние терминальным
для i от 1 до n:
занулить массив B
для каждой вершины v из [1..V]:
для каждого символа s из алфавита:
B[g(v, s)] += A[v]
поменять массивы A и B местами
выдать A[root]
Здравствуйте, Кузнец, Вы писали:
К> то сложность возведения матрицы в степень будет n*n*n * log(N) (используем бинарное возведение в степень), при n = 2000 это слишком много (кубическая сложность).
Матрицы в квадрат можно и не за куб возводить. Тем же алгоритмом Винограда—Штрассена, например. Не квадратичная сложность, но всё же.
Здравствуйте, Кузнец, Вы писали:
Pzz>>Очевидно, что задача решается с помощью детерминированного регулярного конечного автомата. Следовательно, время обработки входного текста можно сделать вообще не зависящим от количества запрещенных слов, и к тому же весьма быстрым (на каждый входной символ — один раз заглянуть в таблицу).
К>Построить по запрещённым словам автомат я могу, как после этого найти количество путей в нём, которые не задевали бы терминальные вершины, и при этом имели бы заданную длину N ?
А это еще зачем? В исходной задаче такого не было.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, Кузнец, Вы писали:
W>Алгоритм — как написано. Простейшая реализация — так:
W>
W>Пусть V - число состояний автомата
W>завести два массива A[V] и B[V]
W>инициализировать массив A значениями 0 или 1 в зависимости от того, является ли соответствующее состояние терминальным
W>для i от 1 до n:
W> занулить массив B
W> для каждой вершины v из [1..V]:
W> для каждого символа s из алфавита:
W> B[g(v, s)] += A[v]
W> поменять массивы A и B местами
W>выдать A[root]
W>
Запрограммировал этот код, но что-то не то выдаёт, видимо я что-то напутал с терминальными вершинами.
Возьмём простой пример, пусть мы ищем слова длины 5, не содержащие одного однобуквенного подслова "a", причём для простоты пусть алфавит состоит из двух букв 'a', 'b'. Ответ в этом случае равен 1 (слов "bbbbb"). Что даст выполнение алгоритма.
Автомат для одного слова "a" состоит из двух вершин и выглядит так:
Заводим два массива A, B, начальное их состояние таково: A = {1, 0}, B = {0, 0}, делаем первый шаг, два прохода по телу цикла, первый проход прибавит ко всем вершинам, в которые можно попасть из 0-вершины, число A[0] = 0, (для символа 'a': B[1] += A[0], 'b': B[0] += A[0], B = {1, 1}), второй проход: из состояния 1 символ 'b' отправит в корень, символ 'a' отправит снова в состояние 1, то есть B[0] += A[1], B[1] += A[0], после этого шага снова B = {1, 1}. Таким образом, после первого шага (после обмена состояний массивов A, B и зануления B) имеем A = {1, 1}, B = {0, 0}. Делаем второй шаг алгоритма, формула для значений в B те же (они зависят только от автомата), а именно: B[0] = A[0] + A[1], B[1] = A[0] + A[1], и после второго шага получим A = {2, 2}, дальше значения в A будут только расти, и ответ 1 не получится никак.
Где я тут прокололся ? Такое впечатление, что не все переходы по автомату надо учитывать...
Здравствуйте, Кузнец, Вы писали:
Pzz>>Очевидно, что задача решается с помощью детерминированного регулярного конечного автомата. Следовательно, время обработки входного текста можно сделать вообще не зависящим от количества запрещенных слов, и к тому же весьма быстрым (на каждый входной символ — один раз заглянуть в таблицу).
К>Построить по запрещённым словам автомат я могу, как после этого найти количество путей в нём, которые не задевали бы терминальные вершины, и при этом имели бы заданную длину N ?
Я наконец осознал, что надо не фильтровать строки на хорошие/плохие на лету, а подсчитать количество хороших строк заданной длинны.
А зачем может понадобиться такое странное число?
Заметим, что задача была бы тривиальной, если бы автомат представлялся ациклическим графом. Проблема именно с циклами. Надо подумать, как наличие цикла влияет на ответ.
Здравствуйте, watchmaker, Вы писали:
W>Это сейчас у тебя рекурсия написана, а в первом сообщении написано про динамику. В динамическом программировании не нужно повторно решать уже решенные задачи. Спуск до единиц произойдёт только при первом переходе от длины 0 к длине 1. Больше они никогда в решении не возникнут.
Вот тут я сильно накосячил, спасибо. У меня действительно была рекурсия, а не DP. Добавил кэш, который хранит значение f(v, n), если оно однажды уже было вычислено, сразу стало работать на моих тестах. Правда не всё так радужно — в тестирующей системе на одном тесте ловлю Time Limit, либо где-то зависание, либо слишком большое дерево и долго алгоритм слишком долго его обходит... пока не знаю...
Здравствуйте, Pzz, Вы писали:
Pzz>Я наконец осознал, что надо не фильтровать строки на хорошие/плохие на лету, а подсчитать количество хороших строк заданной длинны.
Pzz>А зачем может понадобиться такое странное число?
Pzz>Заметим, что задача была бы тривиальной, если бы автомат представлялся ациклическим графом. Проблема именно с циклами. Надо подумать, как наличие цикла влияет на ответ.
Это учебная задача по программированию на применение автоматов.
Если бы автомат был без циклов, то да, удалили все терминальные состояния и посчитали, сколько осталось состояний ) Если есть циклы (они же, откаты), то всё хитрее, но не сильно. Нужно посчитать количество путей заданной длины в графе, которые выходят из корня и не проходят по терминалам (запрещённые вершины, её посещение означает, что в нашей строке нашлась запрещённая подстрока). Удалим из графа все запрещённые вершины, а полученный граф будем анализировать с точки зрения числа путей. Тут я и применил алгоритм с матрицей — матрицу смежности возводим в нужную степень и считаем у неё сумму элементов столбца, соответствующего вершине root, это и будет ответом. Матрицу можно возвести в степень за O(n^3 * log(k)) — бинарным алгоритмом, выше был предложен более быстрый алгоритм за O(n^{2.8} * log(k)) (с показателем мог чуть ошибиться, он точно меньше 3), но это всё равно слишком долго, крайние случаи n = 2000 и k = 1000. Тут только квадратичный алгоритм (скорее всего)...
Здравствуйте, Кузнец, Вы писали:
К>Такое впечатление, что не все переходы по автомату надо учитывать...
Да, переходы надо учитывать не все. Можно это место так поправить: для каждой нетерминальной вершины v из [1..V]
Ну и проверить, что нужно писать B[g(v, s)] += A[v] а не наоборот B[v] += A[g(v, s)]
Здравствуйте, Кузнец, Вы писали: К>Этот алгоритм можно как-то ускорить ? И если нет, то подкиньте хотя бы идею, как эту задачу можно решить...
сложно представить для чего нужно именно точное количество таких слов
вы точно ту задачу решаете? может, сойдет приблизительное или вообще количество не нужно?
Здравствуйте, Кузнец, Вы писали:
К>Если бы автомат был без циклов, то да, удалили все терминальные состояния и посчитали, сколько осталось состояний ) Если есть циклы (они же, откаты), то всё хитрее, но не сильно. Нужно посчитать количество путей заданной длины в графе, которые выходят из корня и не проходят по терминалам (запрещённые вершины, её посещение означает, что в нашей строке нашлась запрещённая подстрока). Удалим из графа все запрещённые вершины, а полученный граф будем анализировать с точки зрения числа путей. Тут я и применил алгоритм с матрицей — матрицу смежности возводим в нужную степень и считаем у неё сумму элементов столбца, соответствующего вершине root, это и будет ответом. Матрицу можно возвести в степень за O(n^3 * log(k)) — бинарным алгоритмом, выше был предложен более быстрый алгоритм за O(n^{2.8} * log(k)) (с показателем мог чуть ошибиться, он точно меньше 3), но это всё равно слишком долго, крайние случаи n = 2000 и k = 1000. Тут только квадратичный алгоритм (скорее всего)...
Матрицу смежности возводить в степень в общем виде здесь не оптимально — она сильно разрежена, ведь у каждой вершины может быть максимум 26 переходов (по числу букв в алфавите). Если просто написать динамику в лоб, должно получиться O(N^2*K*A), где N — количество состояний в автомате, К — длина слова, А — размер алфавита.
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, Кузнец, Вы писали: К>>Этот алгоритм можно как-то ускорить ? И если нет, то подкиньте хотя бы идею, как эту задачу можно решить... __>сложно представить для чего нужно именно точное количество таких слов __>вы точно ту задачу решаете? может, сойдет приблизительное или вообще количество не нужно?
Это учебная задача ) На самом деле в задаче нужно число слов по какому-то модулю (точное число не помню), но это дополнение не по существу — каждый раз при выполнении сумм и произведений в динамике приводить по модулю это мелкое изменение, поэтому я не стал о нём упоминать )
