# Re: Determining the common prefix for several strings

**URL:** <https://www.ruby-forum.com/t/re-determining-the-common-prefix-for-several-strings/111347>\
**Category:** Ruby\
**Created:** [August 6, 2007, 12:09pm UTC](https://www.ruby-forum.com/t/re-determining-the-common-prefix-for-several-strings/111347 "2007-08-06T12:09:48Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![stickstone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/6f9a4e/32.png) [@stickstone](https://www.ruby-forum.com/u/stickstone)\
**Post date:** [August 6, 2007, 12:09pm UTC](https://www.ruby-forum.com/t/re-determining-the-common-prefix-for-several-strings/111347/1 "2007-08-06T12:09:48Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![stickstone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/6f9a4e/32.png) [@stickstone](https://www.ruby-forum.com/u/stickstone)\
**Post date:** [August 6, 2007, 12:28pm UTC](https://www.ruby-forum.com/t/re-determining-the-common-prefix-for-several-strings/111347/2 "2007-08-06T12:28:50Z")

</div>

On 8/6/07, Brian C. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![stickstone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/6f9a4e/32.png) [@stickstone](https://www.ruby-forum.com/u/stickstone)\
**Post date:** [August 7, 2007, 11:24am UTC](https://www.ruby-forum.com/t/re-determining-the-common-prefix-for-several-strings/111347/3 "2007-08-07T11:24:27Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![stickstone](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/6f9a4e/32.png) [@stickstone](https://www.ruby-forum.com/u/stickstone)\
**Post date:** [August 8, 2007, 4:15am UTC](https://www.ruby-forum.com/t/re-determining-the-common-prefix-for-several-strings/111347/4 "2007-08-08T04:15:36Z")

</div>

From: Brian C. [[mailto:removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)]

# 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