From: Robert Klemme <shortcutter@...>
Date: 2007-08-03T20:39:05+09:00
Subject: Re: Determining the common prefix for several strings

------=_Part_88475_10524956.1186141149128
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

2007/8/3, Daniel DeLorme <dan-ml@dan42.com>:
> > El Aug 3, 2007, a las 2:31 AM, Todd Burch escribi=F3:
> >
> >> I have several strings to analyze.  The strings are the names of a lis=
t
> >> of things that were once ordered and now are not.  A typical array of
> >> names might look like this:
> >>
> >> item001
> >> item004
> >> item002
> >> item002b
> >> item002C
> >> item 5
> >> item 10
> >> itemize this
> >>
> >> I want to parse these names and determine that "item" is the common
> >> prefix.
>
> Haha! Regexp magic!
>
> list =3D <<-EOS
> item001
> item004
> item002
> item002b
> item002C
> item 5
> item 10
> itemize this
> EOS
>
> /\A(.*).*(\n\1.*)*\Z/.match(list)[1]
> =3D> "item"

Amazing!  I wonder how this performs for large input sets (because of
the two ".*" and the "()*"). Could generate a lot of backtracking
(apart from the string length itself).

This is probably better in terms of individual comparisons.  The idea
is to reduce the prefix length whenever a mismatch is found
(attached). That solution also avoids sorting and multiple traversal
of the input in general. So it's suited for stream based processing
(i.e. for reading large files in one go).

Kind regards

robert

------=_Part_88475_10524956.1186141149128
Content-Type: application/x-ruby; name=pref.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f4wlpdak
Content-Disposition: attachment; filename="pref.rb"

bGlzdCA9IDw8LUVPUy50b19hCml0ZW0wMDEKaXRlbTAwMQppdGVtMDA0Cml0ZW0wMDIKaXRlbTAw
MmIKaXRlbTAwMkMKaXRlbSA1Cml0ZW0gMTAKaXRlbWl6ZSB0aGlzCkVPUwoKcHJlZiA9IGxpc3Qu
c2hpZnQKbGlzdC5lYWNoIGRvIHxzfAogIGkgPSAwCiAgd2hpbGUgcHJlZltpXSA9PSBzW2ldICYm
IGkgPCBwcmVmLnNpemUKICAgIGkgKz0gMQogIGVuZAogIHByZWYuc2xpY2UhIGkuLi0xCmVuZApw
IHByZWYK
------=_Part_88475_10524956.1186141149128--