Hi,
Is there any ruby built-in that might tell me how
many characters match (are in common) from the start
(left) of two strings? E.g.
"abcxxxxxx".lcommon("abcdezzzzz") # => "abc" (or 3)
All I need is the length but a substring would be
fine too.
Figured I'd ask in case I'd overlooked a nicer way
to do this than writing a loop. 
Thanks,
Regards,
Bill
.I don't know of anything in built but you could implement Suffix
Trees (http://www.dogma.net/markn/articles/suffixt/suffixt.htm\) to do
this I would guess.
Farrel
On 5/16/05, Bill Kelly <billk@cts.com> wrote:
Hi,
Is there any ruby built-in that might tell me how
many characters match (are in common) from the start
(left) of two strings? E.g."abcxxxxxx".lcommon("abcdezzzzz") # => "abc" (or 3)
All I need is the length but a substring would be
fine too.Figured I'd ask in case I'd overlooked a nicer way
to do this than writing a loop.Thanks,
Regards,
Bill
"Bill Kelly" <billk@cts.com> schrieb im Newsbeitrag news:020b01c559ef$fc194ee0$6442a8c0@musicbox...
Hi,
Is there any ruby built-in that might tell me how
many characters match (are in common) from the start
(left) of two strings? E.g."abcxxxxxx".lcommon("abcdezzzzz") # => "abc" (or 3)
All I need is the length but a substring would be
fine too.Figured I'd ask in case I'd overlooked a nicer way
to do this than writing a loop.
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"
Kind regards
robert
I don't know of anything in built but you could implement Suffix
Trees (http://www.dogma.net/markn/articles/suffixt/suffixt.htm\) to do
this I would guess.
Yeah, but sounds like overkill (reading the strings already takes O(n),
comparing the start is also O(n)).
otoh, if you need to do this more often/for more than two strings,
suffix trees might be useful.
Did zedas release his suffix tree stuff separately?
If not, look in fastcst and odeum (guessing about odeum, sorry zedas
+--- Kero ------------------------- kero@chello@nl ---+
all the meaningless and empty words I spoke |
Promises -- The Cranberries |
+--- M38c --- http://members.chello.nl/k.vangelder ---+
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)
+--- Kero ------------------------- kero@chello@nl ---+
all the meaningless and empty words I spoke |
Promises -- The Cranberries |
+--- M38c --- http://members.chello.nl/k.vangelder ---+
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
Heheheheheheheh.... Nice. 
Regards,
Bill
From: "Robert Klemme" <bob.news@gmx.net>
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
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)
--
http://ruby.brian-schroeder.de/
Stringed instrument chords: http://chordlist.brian-schroeder.de/
Hi --
class String
def lcommon(other)
0.upto(length) do | i | return i if other[i] != self[i] end
length
end
end
You can also use the return value of times to do this:
class String
def lcommon(other)
length.times do |i| return i if other[i] != self[i] end
end
end
(I had been toying with this but using break instead of return, which
was giving me problems
David
On Mon, 16 May 2005, [ISO-8859-1] Brian Schr枚der wrote:
--
David A. Black
dblack@wobblini.net
"David A. Black" <dblack@wobblini.net> schrieb im Newsbeitrag news:Pine.LNX.4.61.0505160448390.24570@wobblini...
Hi --
class String
def lcommon(other)
0.upto(length) do | i | return i if other[i] != self[i] end
length
end
end
You can also use the return value of times to do this:
class String
def lcommon(other)
length.times do |i| return i if other[i] != self[i] end
end
end
(I had been toying with this but using break instead of return, which
was giving me problems
Hey, this is nice!
robert
On Mon, 16 May 2005, [ISO-8859-1] Brian Schr枚der wrote:
> class String
> def lcommon(other)
> 0.upto(length) do | i | return i if other[i] != self[i] end
> length
> end
> endYou can also use the return value of times to do this:
class String
def lcommon(other)
length.times do |i| return i if other[i] != self[i] end
end
end
Cool solutions, guys - thanks !
Regards,
Bill
From: "David A. Black" <dblack@wobblini.net>
On Mon, 16 May 2005, [ISO-8859-1] Brian Schr枚der wrote: