Сколько раз каждое слово
Составителю частотного словаря нужно знать, сколько раз каждое слово из списка встречается в тексте — не как отдельное слово, а как подстрока, вместе с перекрытиями: в «абракадабре» «абра» встречается дважды, «а» — пять раз. Слов в списке тысячи, и текст длинный, поэтому искать каждое отдельно слишком долго.
Среди тестов — начало первой части «Войны и мира» со словарём романа, геном фага λ со всеми словами из четырёх букв ДНК и текст, в котором вхождений больше восьмидесяти миллионов.
Вход
В первой строке — текст длиной от 1 до 200 000 знаков; знаки любые, кроме перевода строки. Во второй — число слов k (1 ≤ k ≤ 20 000). Дальше k строк, по слову в каждой: слово непустое, может содержать пробелы внутри, но не начинается и не заканчивается пробелом. Суммарная длина слов не больше 100 000. Слова могут повторяться.
Выход
k строк: для каждого слова в порядке входа — число позиций текста, с которых оно начинается.
Примеры
Пример 1
ushers 4 he she his hers
1 1 0 1
Пример 2
абракадабра 8 а абра бра кад ра дабр абракадабра я
5 2 2 1 2 1 1 0
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Постройте автомат Ахо — Корасик из всех слов. Он за один проход перечисляет все вхождения. Сколько их может быть в худшем случае?
2Подсказка 2
Возьмите текст из двухсот тысяч букв a и слова a, aa, aaa, … — сколько найдёт перечисление? Около 446 вхождений на каждую позицию, почти 90 миллионов. Нужно считать, не перечисляя.
3Подсказка 3
Если автомат стоит в узле v, в этой позиции кончаются слова всех узлов на цепочке ссылок отказа от v до корня. Запишите в каждый узел, сколько раз автомат в нём стоял, и подумайте, как разнести эти числа по цепочкам за один обход.
4Идея
Число вхождений слова, которое кончается в узле u, — это сколько раз автомат стоял в узлах, из которых цепочка ссылок отказа проходит через u. Ссылки отказа образуют дерево с корнем в корне бора, и нужная сумма — сумма по поддереву u в этом дереве. Её считают, обходя узлы от глубоких к мелким и прибавляя число каждого узла к числу его ссылки отказа.
5Разбор
Строим бор и ссылки отказа обходом в ширину, запоминая порядок обхода: ссылка отказа любого узла ведёт в узел, который обойдён раньше. Проходим текст и в массиве hits считаем, сколько раз автомат остановился в каждом узле после очередной буквы. Затем идём по узлам в обратном порядке обхода и делаем hits[fail[u]] += hits[u]: когда очередь доходит до узла, все узлы, чьи цепочки проходят через него, уже отдали ему свои числа. Ответ для слова — hits узла, где оно кончается. Повторы слов и слова, которые нигде не встретились, обрабатываются сами собой.
Посмотрите на четвёртый тест: в начале первой части «Пьер» встречается 242 раза, а «Пьера» — 45, и все 45 вхождений «Пьера» входят в эти 242: подстрока «Пьер» есть внутри «Пьера». Как отдельное слово «Пьер» встречается реже, и в статье о ловушках автомата показано, как это проверить.
5+Решение
6Сложность
O(n + Σ|wi|) времени и O(Σ|wi|) памяти: построение, один проход по тексту и один обход узлов. Перечисление вхождений по словарным ссылкам стоит O(n + Σ|wi| + z), а в пятом тесте z = 89 100 765.
7Типичные ошибки
- Перечислять вхождения. Правильно, но на тексте из одной буквы и словах из её повторов — десятки миллионов шагов, в Python это секунды.
- Только слово самого узла. Если в узле v прибавлять только словам, которые кончаются ровно в v, теряются вложенные: в ushers автомат стоит в узле she, а he тоже кончается здесь.
- Не тот порядок. Прибавлять к ссылке отказа в порядке номеров узлов нельзя: узел может отдать своё число раньше, чем получит числа от более глубоких. Нужен обратный порядок обхода в ширину, по убыванию глубины.
str.countпо каждому слову. Не считает перекрытия и стоит O(n) на слово — двадцать тысяч проходов по двумстам тысячам знаков.
Алгоритмы задачи
O(n + Σ|wᵢ| + z)
1 задача
DS
Структура данных
Бор (префиксное дерево)
Слова с общим началом идут общим путём: поиск слова и всех продолжений — за длину запроса.
O(L) на вставку и поиск слова длины L
2 задачи