[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

determining common characters from start of two strings?

Bill Kelly

5/16/2005 8:18:00 AM

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
17 Answers

Farrel Lifson

5/16/2005 10:05:00 AM

0

I don't know of anything in built but you could implement Suffix
Trees (http://www.dogma.net/markn/articles/suffixt/s...) 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
>
>

Robert Klemme

5/16/2005 10:47:00 AM

0


"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

Kero van Gelder

5/16/2005 10:51:00 AM

0

> I don't know of anything in built but you could implement Suffix
> Trees (http://www.dogma.net/markn/articles/suffixt/s...) 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... ---+

Kero van Gelder

5/16/2005 11:14:00 AM

0

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

Brian Schröder

5/16/2005 11:33:00 AM

0

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-sch...

Stringed instrument chords: http://chordlist.brian-sch...

dblack

5/16/2005 11:51:00 AM

0

Robert Klemme

5/16/2005 4:54:00 PM

0


"David A. Black" <dblack@wobblini.net> schrieb im Newsbeitrag
news:Pine.LNX.4.61.0505160448390.24570@wobblini...
Hi --

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

Bill Kelly

5/16/2005 4:55:00 PM

0

From: "Robert Klemme" <bob.news@gmx.net>
>
> 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

5/16/2005 5:16:00 PM

0

From: "David A. Black" <dblack@wobblini.net>
>
> 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
> > 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

Cool solutions, guys - thanks !


Regards,

Bill

JohnPaulPontiff

7/31/2013 4:34:00 PM

0


Hey,

On Wednesday, July 31, 2013 1:55:04 AM UTC-4, Ishkabibble wrote:
> imgur album

Thanks! [clicks] *undrilled apocalyptic megabarrels*
0/10 - Would not Zerg-rush with Chaos Hammernators.

http://s15.postimg.org/ajd1pzli3/Doin_I...

> legal clamor

[Titan Guy trollfaces the camera and whispers, "Chapter House."]

http://s24.postimg.org/lz4pmnomt/1_...

Winston & Strawn beat GW's Legal team like a rented mule.

http://s12.postimg.org/sj9snm98t/2...

Imaginary enemies didn't Kill GW's bits service - GW did.
Afaik, *making* models and parts isn't even an issue now.

http://s18.postimg.org/vht1l507t/Bi...

> possible Streisand Effect

GW has finally been schooled on -
* trademarking terms and symbols that they obviously didn't invent
* routinely bullying cottage-industrialists because why not
* pretending that the things they sell are't just TOYS
* bringing frivolous lawsuits when you don't know law

Just don't sell whole GW models made by someone else.
Unless you live in some place beyond GW's reach ...


Playa