Задачник Базовый курс EN

Текст без пробелов

мемоизация динамика хеш-таблица подсчёт вариантов редакторы текста

Из текста убрали пробелы и знаки препинания. Сколькими способами его можно снова разрезать на слова словаря? Ответ бывает огромным, поэтому выведите его остаток от деления на 10⁹ + 7.

Со второго теста словарь — 14 871 слово «Войны и мира», которые встречаются в романе хотя бы трижды, и однобуквенные а, в, и, к, о, с, у, я. Тексты — фразы и абзацы романа. «Наполеон» читается двумя способами: «наполеон» и «на поле он».

Вход

В первой строке m — число слов словаря, во второй — сами слова через пробел (не длиннее 24 букв). Дальше q (1 ≤ q ≤ 30) и q строк — тексты длиной до 5000 букв. Все слова и тексты — из строчных русских букв.

Выход

Для каждого текста — число способов по модулю 10⁹ + 7.

Примеры

Пример 1

Вход

4
а б аб ба
3
абаб
ба
в

Выход

5
2
0

Ограничения

Время · Python: 5000 мс
Время · Go: 1500 мс
Память: 256 МБ
Проверка: 7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Пусть ways(i) — число способов дочитать текст, начиная с буквы i. Как выразить его через ways с бо́льшими номерами? И сколько раз рекурсия будет считать одно и то же ways(i)?

2Идея

ways(i) — это сумма ways(j) по всем j, для которых кусок текста с i по j − 1 — слово словаря; ways(n) = 1. Рекурсия прямо по этой формуле верна, но к одной и той же позиции приходит разными дорогами — столько раз, сколькими способами можно прочитать начало. Если запоминать ответ для каждой позиции, каждая считается один раз.

3Разбор

С памятью позиций n + 1, на каждую — не больше 24 проверок «есть ли такое слово»: хеш-таблица отвечает за O(1) в среднем. Удобно заполнять таблицу ways с конца, без рекурсии: на тексте в 5000 букв рекурсия ушла бы на глубину 5000, а предел Python по умолчанию — тысяча вызовов.

Без памяти абзац о Наташе из статьи потребовал бы 3,4·10¹¹ вызовов. С памятью — 133 позиции.

Остаток берите на каждом шаге: иначе в Go числа переполнятся, а в Python станут огромными и медленными.

3+Решение

4Сложность

O(n·L) проверок на текст длины n, где L = 24 — длина самого длинного слова; плюс время на хеширование кусков.

5Типичные ошибки

Рекурсия без памяти. Верна, но экспоненциальна: на абзацах четвёртого теста не дождаться.
Глубокая рекурсия с памятью. На шестом тесте 5000 вложенных вызовов: в Python без sys.setrecursionlimit это RecursionError. Таблица с конца обходится без рекурсии.
Остаток только в конце. Числа растут как экспонента от длины текста; брать остаток нужно при каждом сложении.

Алгоритмы задачи

TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи