From: Xavier Noria <fxn@...>
Date: 2007-08-04T00:46:27+09:00
Subject: Re: Determining the common prefix for several strings

El Aug 3, 2007, a las 3:39 PM, Xavier Noria escribi�:

> El Aug 3, 2007, a las 1:35 PM, Xavier Noria escribi�:
>
>>   prefix = ''
>>   min, max = items.sort.values_at(0, -1)
>>   min.split(//).each_with_index do |c, i|
>>     break if c != max[i, 1]
>>     prefix << c
>>   end
>>   puts prefix
>
> Yet another iteration: the prefix can be extracted with a regexp,  
> it's shorter although perhaps more obscure:
>
>   min, max = items.sort.values_at(0, -1)
>   puts min+max =~ /(.).{#{min.length-1}}(?!\1)/m ? $` : min
>
> I don't like the ternary and the fact that we look for the first  
> mismatch instead of extracting directly the prefix in one shot.

This is a direct way:

   min, max = items.sort.values_at(0, -1)
   puts (min+max).match(/\A(.*).*(?=.{#{max.length}}\z)\1/m)[1]

Of course if you can rely on some character that does no belong to  
the items that's easier, it just takes a simplification of Daniel's  
in the case of "\n":

   min, max = items.sort.values_at(0, -1)
   puts "#{min}\n#{max}".match(/^(.*).*\n\1/)[1]

Albeit those positive approaches are direct they backtrack quite a  
lot, perhaps the fixed-length look-ahead with \z in the latter may  
get some optimization, I don't knw. On the contrary the negative  
approach, the one that looks for a mismatch, does not backtrack at  
all, in that sense that's the direct one.

Anyway, I doubt I'd use a regexp approach in production code.

-- fxn