прикреплённый файл:hash744.py к странице LecturesVMSH/2011-05-04

   1 #!/usr/bin/python
   2 # coding: utf8
   3 '''
   4 Реализуйте структуру данных типа “множество строк”. Хранимые строки  – непустые последовательности  длиной не более 10 символов, состоящие из строчных латинских букв.
   5 Структура данных должна поддерживать операции добавления строки в множество и проверки принадлежности  данной строки множеству.
   6 Максимальное количество элементов в хранимом множестве не превосходит 106.
   7 
   8 Формат входных данных
   9 
  10 Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция.
  11 Тип операции  – один из двух символов:
  12     +  означает добавление данной строки в множество;  
  13     ?  означает проверку принадлежности данной строки множеству.
  14 Общее количество операций во входном файле не превосходит 106. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных.
  15 При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве.
  16 
  17 Формат выходных данных
  18 Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.
  19 
  20 Пример
  21 Входные данные
  22 + hello
  23 ? hello
  24 ? bye
  25 + bye
  26 ? bye
  27 #
  28 
  29 Выходные данные
  30 YES
  31 NO
  32 YES
  33 '''
  34 
  35 import random, sys
  36 MAX=10**6
  37 VOL=10**5
  38 S=[chr(c) for c in range(ord('a'),ord('z')+1)]
  39 
  40 if len(sys.argv) > 1: # Генератор входных данных
  41     L=[]
  42     for i in xrange(random.randrange(MAX/2,MAX)):
  43         c=random.randrange(3)
  44         if not L or c==0:
  45             L.append("".join(random.sample(S,random.randrange(2,11))))
  46             print "+",L[-1]
  47         elif c==1:
  48             print "?",random.choice(L)
  49         else:
  50             s="".join(random.sample(S,random.randrange(2,11)))
  51             print "?",s
  52     print "#"
  53     sys.exit(0)
  54 
  55 def Hash(s):
  56     i=0
  57     for c in s:
  58         i=i*31337+ord(c)-ord('a')
  59     return i%VOL
  60     #return reduce(lamda s,c: s*31337+ord(c)-ord('a'),s,0)%VOL
  61     #return sum([ord(c) for c in s])
  62     #return hash(s)
  63 
  64 # Абсолютно бессмысленный класс. Dict всё равно лучше
  65 class HashTable:
  66     def __init__(self):
  67         self.table=[[] for i in xrange(VOL)]
  68     def append(self, s):
  69         self.table[Hash(s)].append(s)
  70     def search(self,s):
  71         for c in self.table[Hash(s)]:
  72             if c == s: return 1
  73         return 0
  74 
  75 Tbl=HashTable()
  76 while True:
  77     arg=raw_input().split(" ")
  78     if   arg[0]=="#": break
  79     elif arg[0]=='+': Tbl.append(arg[1])
  80     else: print ["NO","YES"][Tbl.search(arg[1])]