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

2007/8/3, Daniel DeLorme <dan-ml@dan42.com>:
> Robert Klemme wrote:
> > 2007/8/3, Daniel DeLorme <dan-ml@dan42.com>:
> >> /\A(.*).*(\n\1.*)*\Z/.match(list)[1]
> >> => "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).
>
> I think it's ok because the .* pattern is always anchored to line
> endings. In this context, .*\n is the equivalent of [^\n]*\n which
> leaves no room for backtracking.

I believe you are wrong.  Look at "\A(.*).*" - there are multiple ways
this can match (including matching \n inside any of the .* parts).
Anchoring does not help much here IMHO.

Kind regards

robert