On 16/05/05, Kero <kero / chello.single-dot.nl> wrote:
> > Regexps can help here - dunno about performance
> >
> > class String
> >   def lcommon(s)
> >     len = s.length
> >     Regexp.new("^" << s.gsub( /./, '(?:\\&' ) << ( ")?" *
> > len ) ).match(self)[0]
> >   end
> > end
> >
> > > s1 = "abcxxxxxx"
> > => "abcxxxxxx"
> > > s2 = "abcdezzzzz"
> > => "abcdezzzzz"
> > > s1.lcommon s2
> > => "abc"
> >
> > :-)
> 
> evil!
> 
> Depending on the complexity of Regexp.new(), this may still be O(n).
> The performance/constant upon that would be low/high, I suppose.
> (specifically the gsub)

To be a bit serious about this:

class String
  def lcommon(other)
    0.upto(length) do | i | return i if other[i] != self[i] end
    length
  end
end

puts "abcxxx".lcommon("abcyyyz") # => 3
puts "".lcommon("")              # => 0 
puts "abc".lcommon("abc")        # => 3
puts "a".lcommon("")             # => 0 
puts "".lcommon("a")             # => 0

best regards,

Brian

-- 
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/