Build the data structure at the heart of every search engine.
What to build
A program that indexes documents and answers queries that require every query word.
Requirements
- Documents are numbered from 1. Lowercase documents and queries and split them on whitespace.
- For each query, print the numbers of the documents that contain every query word, in increasing order separated by spaces, or
no match.
Input
Line 1: n. Then n documents. Then q, and q queries, one per line.
Output
q lines.
Constraints
n ≤ 1,000; q ≤ 100; every query has at least one word.
Example
Input:
3
cheap flights to paris
paris hotels and cheap rooms
learn python
3
cheap paris
python
cheap python
Output:
1 2
3
no match
Why it works
The index stores, for each word, the sorted list of documents that contain it, so an AND query only needs to intersect a few short lists instead of reading every document.
Examples
3 cheap flights to paris paris hotels and cheap rooms learn python 3 cheap paris python cheap python
1 2 3 no match
2 The cat the dog 1 THE
1 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
While reading document i, append i to a word's postings only if the list does not already end with i.
Hint 2
Start with the postings of the first query word and keep only the documents that are also in each other word's postings.
Solution
Show one correct solution (try it yourself first)
n = int(input())
index = {}
for i in range(1, n + 1):
for w in input().lower().split():
postings = index.setdefault(w, [])
if not postings or postings[-1] != i:
postings.append(i)
for _ in range(int(input())):
words = input().lower().split()
result = index.get(words[0], [])
for w in words[1:]:
other = index.get(w, [])
result = [d for d in result if d in other]
print(" ".join(map(str, result)) if result else "no match")