В этой задаче можно пользоваться хеш-таблицами из стандартных библиотек.
Тимофей пишет свою поисковую систему.
Имеется n документов, каждый из которых представляет собой текст из слов. По этим документам требуется построить поисковый индекс. На вход системе будут подаваться запросы. Запрос —– некоторый набор слов. По запросу надо вывести 5 самых релевантных документов.
Релевантность документа оценивается следующим образом: для каждого уникального слова из запроса берётся число его вхождений в документ, полученные числа для всех слов из запроса суммируются. Итоговая сумма и является релевантностью документа. Чем больше сумма, тем больше документ подходит под запрос.
Сортировка документов на выдаче производится по убыванию релевантности. Если релевантности документов совпадают —– то по возрастанию их порядковых номеров в базе (то есть во входных данных).
Подумайте над случаями, когда запросы состоят из слов, встречающихся в малом количестве документов. Что если одно слово много раз встречается в одном документе?
В первой строке дано натуральное число n —– количество документов в базе (1 ≤ n ≤ 104).
Далее в n строках даны документы по одному в строке. Каждый документ состоит из нескольких слов, слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Длина одного текста не превосходит 1000 символов. Текст не бывает пустым.
В следующей строке дано число запросов —– натуральное число m (1 ≤ m ≤ 104). В следующих m строках даны запросы по одному в строке. Каждый запрос состоит из одного или нескольких слов. Запрос не бывает пустым. Слова отделяются друг от друга одним пробелом и состоят из маленьких латинских букв. Число символов в запросе не превосходит 100.
Для каждого запроса выведите на одной строке номера пяти самых релевантных документов. Если нашлось менее пяти документов, то выведите столько, сколько нашлось. Документы с релевантностью 0 выдавать не нужно.
|
3 i love coffee coffee with milk and sugar free tea for everyone 3 i like black coffee without milk everyone loves new year mary likes black coffee without milk |
1 2 3 2 1 |
|
6 buy flat in moscow rent flat in moscow sell flat in moscow want flat in moscow like crazy clean flat in moscow on weekends renovate flat in moscow 1 flat in moscow for crazy weekends |
4 5 1 2 3 |
|
3 i like dfs and bfs i like dfs dfs i like bfs with bfs and bfs 1 dfs dfs dfs dfs bfs |
3 1 2 |