прикреплённый файл:2013-04-26.multisearch.py к странице LecturesVMSH/Python/2013-04-26

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Реализовать поиск множества строк по одной строке
   5 См. http://www.chiark.greenend.org.uk/~sgtatham/algorithms/blocksort.html
   6 Ответ -- True или False
   7 '''
   8 
   9 import sys
  10 # Это уже реализовааная нами функция сортировки слиянием
  11 from joinsort import joinsort
  12 
  13 def create_table(name, s):
  14     '''Подготовка таблицы поиска по строке s.
  15     ВНИМАНИЕ: строка не должна соджержать переводов строки'''
  16     f=open(name,"w")
  17     for i in xrange(1,len(s)):
  18         f.write(s[-i:]+"\n")
  19     f.close()
  20     joinsort(name)
  21 
  22 def search_table(name, word):
  23     '''Поиск подстроки в сортированном файле методом половинного деления'''
  24     f=open(name)
  25     f.seek(0,2)         # конец файла
  26     size=f.tell()
  27     pos,offset,direction=size/2,size/2,1
  28     ret=True
  29     while offset:
  30         f.seek(pos)
  31         f.readline()
  32         s=f.readline()
  33         if s and s.startswith(word):
  34             break
  35         if s>word or not s:
  36             direction=-1
  37         else:
  38             direction=1
  39         offset/=2
  40         pos+=offset*direction
  41     else:
  42         ret=False
  43     f.close()
  44     return ret
  45 
  46 # Имя файла с таблицей похоже на имя программы
  47 TName=sys.argv[0]+".data"
  48 # если параметров нет, читаем со стандартного ввода строку и готовим таблицу
  49 if len(sys.argv)<2:
  50     S=sys.stdin.read()
  51     create_table(TName,S)
  52 # иначе ищем подстроку argv[1] в таблице
  53 else:
  54     print search_table(TName,sys.argv[1])