Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.22 KB | None | 0 0
  1. #!/bin/python3
  2.  
  3. import math
  4. import os
  5. import random
  6. import re
  7. import sys
  8.  
  9.  
  10. class HTBackedSet:
  11.     def __init__(self):
  12.         self.hash_table = LinearProbingHashMap()
  13.         self.present = object()
  14.  
  15.     def add(self, value):
  16.         self.hash_table[value] = self.present
  17.  
  18.     def __contains__(self, value):
  19.         try:
  20.             _ = self.hash_table[value]
  21.             return True
  22.         except KeyError:
  23.             return False
  24.  
  25.     def __str__(self):
  26.         return ' '.join([str(key) for key, value in self.hash_table])
  27.  
  28.  
  29. class LinearProbingHashMap:
  30.     def __init__(self, initial_capacity=2500):
  31.         self.keys = [None] * initial_capacity
  32.         self.values = [None] * initial_capacity
  33.         self.capacity = initial_capacity
  34.  
  35.     def find_index(self, key):
  36.         return key.__hash__() % self.capacity
  37.  
  38.     def __contains__(self, key):
  39.         try:
  40.             value = self[key]
  41.             return True
  42.         except KeyError:
  43.             return False
  44.  
  45.     def __setitem__(self, key, value):
  46.         i = self.find_index(key)
  47.  
  48.         while self.keys[i] is not None:
  49.             if self.keys[i] == key:
  50.                 break
  51.             i = (i + 1) % self.capacity
  52.  
  53.         self.keys[i] = key
  54.         self.values[i] = value
  55.  
  56.     def __getitem__(self, key):
  57.         i = self.find_index(key)
  58.  
  59.         while self.keys[i] is not None:
  60.             if self.keys[i] == key:
  61.                 return self.values[i]
  62.             i = (i + 1) % self.capacity
  63.  
  64.         raise KeyError(key)
  65.  
  66.     def __iter__(self):
  67.         for idx, key in enumerate(self.keys):
  68.             if key is not None:
  69.                 yield key, self.values[idx]
  70.  
  71.     def __str__(self):
  72.         return '\n'.join([f'key = {key}, value = {value}' for key, value in self])
  73.  
  74.  
  75. map1 = LinearProbingHashMap()
  76. set_with_doc = HTBackedSet()
  77. n = int(input())
  78. for i in range(n):
  79.     set_with_doc = HTBackedSet()
  80.     s = input().split()
  81.     for k in s:
  82.         if k in map1:
  83.             map1[k].add(i)
  84.         else:
  85.             set_with_doc.add(i)
  86.             map1[k] = set_with_doc
  87. m = int(input())
  88. for i in range(m):
  89.     k = input()
  90.     if k in map1:
  91.         print(map1[k])
  92.     else:
  93.         print(-1)
  94. print(map1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement