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

Shift-ORってのはshiftしてORとって、どんどこどんどこと0を左送りにしていって最後まで0送りできた場合にパターンマッチ成功。最後がマッチしたかどうかは補数(一番左が0で残りが1)のANDをとって0が帰ってくるかどうかで判断するという文字列検索アルゴリズム。

#!/usr/bin/env python

def shift_OR_exact (T,P):

   text_length = len(T)
   pattern_length = len(P)

   if pattern_length > text_length: return -1
   if pattern_length == text_length: return 0
   if pattern_length == 1: return T.find(P)

   m1b = (1 << pattern_length ) -1
   table = [m1b] * 256

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

   watch = 1 << ( pattern_length - 1 )

   for i in range(text_length):
       i = T.find(P[0],i)
       if i == -1: return -1

       state = m1b

       while i < text_length:
           state = ( state << 1 ) | table[ord(T[i])]
           if ( state & watch ) == 0:
               return i - pattern_length + 1

           if state == m1b: break
           i += 1

   return -1

if __name__ == '__main__':
   print shift_OR_exact("perlpypythonruby","python")

• ビット演算はperlもpythonも似た感じ
• perlのindexはpythonのfind(こっちは組み込みのメソッド)