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


 

Forums >

comp.lang.ruby

Re: Determining the common prefix for several strings

Brian Candler

8/6/2007 10:01:00 AM

Here's a simple solution from my simple brain. It just takes the common
prefix between the first two items, then the common prefix between this and
the third, etc.

arr = %w{
item001
item004
item002
item002b
item002C
item_5
item_10
itemize_this
}

prefix = arr.first.dup
arr[1..-1].each do |e|
prefix.slice!(e.size..-1) if e.size < prefix.size # optimisation
prefix.chop! while e.index(prefix) != 0
end
puts prefix
3 Answers

Martin DeMello

8/6/2007 10:28:00 AM

0

On 8/6/07, Brian Candler <B.Candler@pobox.com> wrote:
> Here's a simple solution from my simple brain. It just takes the common
> prefix between the first two items, then the common prefix between this and
> the third, etc.

Same solution I came up with, though I missed the size-check
optimisation. Nice because it's strictly linear in (length of the list
+ size of the first word).

martin

Brian Candler

8/7/2007 9:15:00 AM

0

> until prefix.empty? or list.all? { |str| str =~ /^#{prefix}/ }
> prefix.chop!
> end

The trouble with that is that it won't work properly if #{prefix} contains
regexp special characters, and it may even bomb out:

irb(main):001:0> prefix = "abc["
=> "abc["
irb(main):002:0> "abc[def" =~ /^#{prefix}/
RegexpError: invalid regular expression; '[' can't be the last character ie. can't start range at the end of pattern: /^abc[/
from (irb):2
irb(main):003:0>

You can use Regexp::escape to fix that, but then you're still building a
regexp every time round the loop. That's why I think String#index is better
here.

Peña, Botp

8/8/2007 2:15:00 AM

0

From: Brian Candler [mailto:B.Candler@pobox.com]
# The trouble with that is that it won't work properly if
# #{prefix} contains regexp special characters, and it may even bomb out:
#
# irb(main):001:0> prefix = "abc[" # => "abc["
# irb(main):002:0> "abc[def" =~ /^#{prefix}/
# RegexpError: invalid regular expression; '[' can't be the
# last character ie. can't start range at the end of pattern: /^abc[/
# from (irb):2

arggh, why didn't i think about that test case? :) Thanks for the enlightenment.

# You can use Regexp::escape to fix that, but then you're still
# building a regexp every time round the loop. That's why I think
# String#index is better here.

indeed, and index is very fast too. but it still cannot beat those pure regex solutions though. the regex solution is short but my feeble mind cannot decipher it yet on why it works best. maybe i wish regex expressions were as readable as ruby :)

kind regards -botp