Mastering Algorithms With Perl
Jon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 3,263 ()
在庫あり。

ビット演算を利用したアルゴリズム。Shift-ADDと違いdifference,insertion,deletionを考慮する。

可能性を論理和として積み上げていってShift-ORみたいなアプローチで評価するとこだと思う。いまいちちゃんと理解できてないが。

   for j in range(1,k+1):
       s[j]  = (r[j] << 1) & Tc
       s[j] |= (r[j-1] | s[j-1]) << 1
       s[j] |= r[j-1]
       s[j] |= 1

あと、perlで@a = @bとやれるところがpythonではa=bとできず、 b = copy.copy(a)なのね。

#!/usr/bin/env python

import copy

def amatch (T,P,k=-1):

   text_length = len(T)
   pattern_length = len(P)
   po2 = map(lambda(x): 1 << x,range(31))

   if k == -1: k = int(pattern_length/10) + 1

   Table = [0] * 256
   for i in range(pattern_length):
       Table[ord(P[i])] |= po2[i]

   r = [0] * (k+1)
   for i in range(1,k+1):
       r[i] = r[i-1] | po2[i-1]

   mb = po2[pattern_length-1]

   s = [0] * (k+1)
   for i in range(text_length):
       s[0] <<= 1
       s[0] |= 1
       Tc = Table[ord(T[i])]
       s[0] &= Tc

       for j in range(1,k+1):
           s[j]  = (r[j] << 1) & Tc
           s[j] |= (r[j-1] | s[j-1]) << 1
           s[j] |= r[j-1]
           s[j] |= 1

       if s[k] & mb:
           return i - pattern_length + 1 if i > pattern_length else 0
       r = copy.copy(s)
   return -1

if __name__ == '__main__':
   print "match: ", amatch("pearl","perl",1)