From: Harry Kakueki <list.push@...>
Date: 2010-09-26T17:33:30+09:00
Subject: Re: Search for a string in another string allowing mismatches

On Wed, Sep 22, 2010 at 9:47 PM, Harry Kakueki <list.push@gmail.com> wrote:
> On Wed, Sep 22, 2010 at 3:07 AM, Janus Bor <janus@urban-youth.com> wrote:
>>
>> Basically, I want to find out if a string contains my search string as a
>> substring. However, a certain amount of mismatches has to be allowed.
>> Here's an example:
>>
>> query string:
>> "acgt"
>>
>> subject string
>> "acctaggg"
>>
>> If no mismatch was allowed, there would be 0 hits.
>> If 1 mismatch was allowed, the query string would match "acct".
>> If 2 mismatches were allowed, the query string would match "acct" and
>> "aggg".
>>
>
> This does not use regular expressions.
> It does not tell you which characters match. It tells you how many.
>
> I don't know if it is useful or fast enough but maybe it will give you
> some ideas.
>
>
> str = "acctaggg"
>
> (0..str.length-4).each do |y|
>  p str.unpack("@#{y}a4")[0].split(//).zip("acgt".split(//)).map{|r|
> r[0]<=>r[1]}.select{|f| f==0}.size
> end
>
>
>
> Harry
>

A little modification of my previous post.
Again, (lack of) speed may be a problem.


class String
  def fuz(m,n) # (string to match, number of matches)
    a = []
    (0..size-4).each do |y|
      t = self[y,4]
      if t.split(//).zip(m.split(//)).map{|r| r[0]<=>r[1]}.select{|f|
f==0}.size>=n
        a << t
      end
    end
    a
  end
end

str = "acctaggg"

p str.fuz("acgt",2) #> ["acct", "aggg"]


Harry