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

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Вычисление z-функции и ¶-функции строки
   5 '''
   6 
   7 import sys
   8 
   9 def zfun(s, debug=False):
  10     '''Вычисление z-функции строки'''
  11     def dump(c):
  12         if not debug: return
  13         print c, "".join((k==l and "<" or " ")+s[k]+(k==r and ">" or " ") for k in xrange(n))
  14         print " ", "".join((k==i and "^{0}^" or " {0} ").format(z[k]) for k in xrange(n))
  15     n=len(s)
  16     z=[0]*n
  17     l=r=0
  18     for i in xrange(1,n):
  19         dump(":")
  20         if i <= r:
  21             z[i] = min (r-i+1, z[i-l])
  22             dump("=")
  23         while i+z[i] < n and s[z[i]] == s[i+z[i]]:
  24             z[i]+=1
  25             dump("+")
  26             # Эта проверка не зависит от цикла, её можно вынести за его пределы
  27             # оставлена тут только для наглядности
  28             if i+z[i]-1 > r:
  29                 l, r = i, i+z[i]-1
  30                 dump("@")
  31     return z
  32 
  33 def pfun(s, debug=False):
  34     '''Вычисление ¶-функции строки'''
  35     def dump(c):
  36         print c,  "".join((k!=j and " {0} " or "<{0}>").format(s[k]) for k in xrange(n))
  37         print " ","".join(" {0} ".format(n) for n in pi)+"^ ^"
  38     n,pi=len(s),[0]
  39     for c in s[1:]:
  40         j=pi[-1]
  41         dump(":")
  42         while j>0 and c!=s[j]:
  43             j=pi[j-1]
  44             dump("<")
  45         if c==s[j]:
  46             j+=1
  47             dump("+")
  48         pi.append(j)
  49     return pi
  50 
  51 def pfun_short(s):
  52     '''Вычисление ¶-функции строки (короткий вариант)'''
  53     n,pi=len(s),[0]
  54     for c in s[1:]:
  55         j=pi[-1]
  56         while j>0 and c!=s[j]: j=pi[j-1]
  57         if c==s[j]: j+=1
  58         pi.append(j)
  59     return pi
  60 
  61 if len(sys.argv)>2:
  62     print eval(sys.argv[2]+"(sys.argv[1],True)")
  63 else:
  64     print zfun(sys.argv[1])
  65     print pfun(sys.argv[1])