Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/bin/python3
- import math
- import os
- import random
- import re
- import sys
- class HTBackedSet:
- def __init__(self):
- self.hash_table = LinearProbingHashMap()
- self.present = object()
- def add(self, value):
- self.hash_table[value] = self.present
- def __contains__(self, value):
- try:
- _ = self.hash_table[value]
- return True
- except KeyError:
- return False
- def __str__(self):
- return ' '.join([str(key) for key, value in self.hash_table])
- class LinearProbingHashMap:
- def __init__(self, initial_capacity=2500):
- self.keys = [None] * initial_capacity
- self.values = [None] * initial_capacity
- self.capacity = initial_capacity
- def find_index(self, key):
- return key.__hash__() % self.capacity
- def __contains__(self, key):
- try:
- value = self[key]
- return True
- except KeyError:
- return False
- def __setitem__(self, key, value):
- i = self.find_index(key)
- while self.keys[i] is not None:
- if self.keys[i] == key:
- break
- i = (i + 1) % self.capacity
- self.keys[i] = key
- self.values[i] = value
- def __getitem__(self, key):
- i = self.find_index(key)
- while self.keys[i] is not None:
- if self.keys[i] == key:
- return self.values[i]
- i = (i + 1) % self.capacity
- raise KeyError(key)
- def __iter__(self):
- for idx, key in enumerate(self.keys):
- if key is not None:
- yield key, self.values[idx]
- def __str__(self):
- return '\n'.join([f'key = {key}, value = {value}' for key, value in self])
- map1 = LinearProbingHashMap()
- set_with_doc = HTBackedSet()
- n = int(input())
- for i in range(n):
- set_with_doc = HTBackedSet()
- s = input().split()
- for k in s:
- if k in map1:
- map1[k].add(i)
- else:
- set_with_doc.add(i)
- map1[k] = set_with_doc
- m = int(input())
- for i in range(m):
- k = input()
- if k in map1:
- print(map1[k])
- else:
- print(-1)
- print(map1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement