Attachment '2013-04-26.count_squeeze.py'

Download

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Подсчитать количество различных подстрок в строке
   5 '''
   6 
   7 def pfun(s):
   8     '''Вычисление ¶-функции строки'''
   9     n,pi=len(s),[0]
  10     for c in s[1:]:
  11         j=pi[-1]
  12         while j>0 and c!=s[j]: j=pi[j-1]
  13         if c==s[j]: j+=1
  14         pi.append(j)
  15     return pi
  16 
  17 def allsubstr(s):
  18     A=1
  19     for i in xrange(2,len(s)+1):
  20         A+=i-max(pfun(s[-i:]))
  21     return A
  22 
  23 def squeeze(s):
  24     d=len(s)-pfun(s)[-1]
  25     if len(s)%d==0:
  26         return d
  27     else:
  28         return len(s)
  29 
  30 S=raw_input("Введите строку: ")
  31 print allsubstr(S), "различных подстрок(и)"
  32 q=squeeze(S)
  33 print "сжатая строка: ",len(S)/q,"*",S[:q]

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.