From: "A. S. Bradbury" <asbradbury@...>
Date: 2006-09-12T21:29:36+09:00
Subject: Re: How about Enumerable#find_pattern?

Well, here's a (not very good) implementation, kind of ported from some python 
code.

module  Enumerable

  def find_pattern(*pat)
    match_length=0
    match_pos=0
    shifts=compute_table(pat)
    self.each do |obj|
      while (match_length >=0) and !(pat[match_length]===obj)
        match_pos+=shifts[match_length]
        match_length-=shifts[match_length]
      end
      match_length+=1
      if match_length == pat.length
        return match_pos
      end
    end
    return nil  # failed match
  end

  private
  def compute_table(pat)
    shifts=Array.new(pat.size)
    shift = 1
    0.upto pat.size do |i|
      a=pat[i-1]
      b=pat[i-shift-1]
      while (shift < i) and (pat[i-1] != pat[i-shift-1])
        shift += shifts[i-shift-1]
      end
      shifts[i]=shift
    end
    return shifts
  end
end

a="aaaabbaabbab".split(//)
a.find_pattern 'a', 'b', 'b'       #=> 3
a.find_pattern 'c'    #=> nil
a.find_pattern /a|b/, 'a', 'b'      #=> 2

The idea is to allow efficient searching for patterns in the elements of any 
Enumerable object, the example above is contrived.

Alex