determining common characters from start of two strings?

[Bill Kelly]

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

 

[Farrel Lifson]

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

 

[Robert Klemme]

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
=> "abc"



Kind regards

robert

 

[Kero]

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 ---+

 

[Kero]

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 ---+

 

[Brian Schröder]

Regexps can help here - dunno about performance

class String
def lcommon(s)
len =3D s.length
Regexp.new("^" << s.gsub( /./, '(?:\\&' ) << ( ")?" *
len ) ).match(self)[0]
end
end

s1 =3D "abcxxxxxx" =3D> "abcxxxxxx"
s2 =3D "abcdezzzzz" =3D> "abcdezzzzz"
s1.lcommon s2

=3D> "abc"

=20
evil!
=20
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 !=3D self end
length
end
end

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

best regards,

Brian

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

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

 

[David A. Black]

--927295978-786337774-1116244267=:24570
Content-Type: MULTIPART/MIXED; BOUNDARY="927295978-786337774-1116244267=:24570"

This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

--927295978-786337774-1116244267=:24570
Content-Type: TEXT/PLAIN; charset=X-UNKNOWN; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

Hi --

class String
def lcommon(other)
0.upto(length) do | i | return i if other !=3D self 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 !=3D self end
end
end

(I had been toying with this but using break instead of return, which
was giving me problems


David

--=20
David A. Black
(e-mail address removed)
--927295978-786337774-1116244267=:24570--
--927295978-786337774-1116244267=:24570--

 

[Robert Klemme]

Hi --

class String
def lcommon(other)
0.upto(length) do | i | return i if other != self 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 != self 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

 

[Bill Kelly]

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

 

[Bill Kelly]

class String
def lcommon(other)
0.upto(length) do | i | return i if other != self 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 != self end
end
end

Cool solutions, guys - thanks !


Regards,

Bill