from heapq import heappush, heappushpop
with open("test.in", "r") as f:
l = f.read().splitlines()
n, root = int(l[0]), ([], [None] * 26) # root - кортеж из пустого буфера и
# списка nil-ссылок на дочерние узлы
hpp = (heappush, heappushpop)
for i in range(1, n + 1):
w, s = l[i].split()
t = (int(s), w)
node = root
for c in w:
child = node[1][ord(c) - 97] # ord('a') == 97
if child is None:
node[1][ord(c) - 97] = child = ([t], [None] * 26)
else:
ww = child[0]
hpp[len(ww) > 9](ww, t)
node = child
for w in l[n + 2:]:
print(" ~ %s" % w)
node = root
for c in w:
child = node[1][ord(c) - 97]
if child is None:
break
node = child
else:
for t in sorted(child[0], reverse=True):
print("%6d %s" % t)from heapq import heappush, heappushpop
with open("test.in", "r") as f:
l = f.read().splitlines() # читаем файл а список строк
n, d = int(l[0]), {} # n из условия, d - словарь (хэштаблица)
hpp = (heappush, heappushpop)
for i in range(1, n + 1): # перебираю инициализирующие строки
w, s = l[i].split() # расщепляю
t = (int(s), w) # создаю кортеж вида (целое, слово)
while w: # пока в слове есть буквы
w = w[:-1] # отрезаю его последнюю букву - так я перебираю префиксы
if w in d: # если префикс уже в словаре
ww = d[w] # ww - это буфер из не более чем 10 кортежей, ...
hpp[len(ww) > 9](ww, t) # добавляю либо вытесняю кортеж с минимальным числом
else:
d[w] = [t] # создаю и добавляю в словарь новый буфер
for w in l[n + 2:]: # перебираю запросы
print(" ~ %s" % w) # вот префикс
if w in d: # если префикс в словаре
for t in sorted(d[w], reverse=True):
print("%6d %s" % t) # печатаю отсортированный буфер