NLP: An inverted index with AND queries

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

Example 1 · Input
3
cheap flights to paris
paris hotels and cheap rooms
learn python
3
cheap paris
python
cheap python
Expected output
1 2
3
no match
Example 2 · Input
2
The cat
the dog
1
THE
Expected output
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")

Lesson: Text similarity and search →