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

これもビット演算を利用したアルゴリズム。differenceを許容するけどinsertion,deletionは駄目。

#!/usr/bin/env python

from math import *

def shift_ADD (T, P, k=-1):
   text_length = len(T)
   pattern_length = len(P)

   if k == -1: k = int(log(text_length)+1)
   if k == 0:  return T.find(P)
   if pattern_length == 1: return T.find(P)
   if pattern_length > text_length: return -1
   if pattern_length == text_length and P == T: return 0

   bits = int(log(k+1,2)) + 1 # ????
   mask = 1 << ( bits - 1 )
   ovmask = 0

   for i in range(pattern_length):
       ovmask |= mask
       mask <<= bits

   table = [ovmask >> (bits-1)] * 256

   nmask = 1
   for i in range(pattern_length):
       table[ord(P[i])] &= ~nmask
       nmask <<= bits

   mask = ( 1 << ( pattern_length * bits )) -1
   state = mask & ~ovmask
   ov = ovmask
   watch = ( k + 1 ) << ( bits  * ( pattern_length - 1 ) )

   for i in range(text_length):
       state = ((state << bits) + table[ord(T[i])]) & mask
       ov    = ((ov << bits) | (state & ovmask))    & mask
       state &= ~ovmask
       if (state | ov) < watch:
           return i - pattern_length + 1

   return -1

if __name__ == '__main__':
   print shift_ADD("perlpethonxx","python",2)