Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I have two strings. For the sake of the example they are set like this:

string1="test toast"
string2="test test"

What I want is to find the overlap starting at the beginning of the strings. With overlap I mean the string "test t" in my above example.

# I look for the command 
command "$string1" "$string2"
# that outputs:
"test t"

If the strings were string1="atest toast"; string2="test test" they would have no overlap since the check starts form the beginning and the "a" at the start of string1 .

share|improve this question

closed as off-topic by Ramesh, chaos, slm Oct 1 at 23:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question has been posted on multiple sites. Cross-posting is strongly discouraged; see the help center and community FAQ for more information." – Ramesh, chaos, slm

    
    
This is exactly the reason people aren't supposed to cross-post; now it has multiple answers on each site that are different, and it's on-topic for both sites. I think I'm just going to leave it here anyway –  Michael Mrozek Aug 8 '11 at 14:15

4 Answers 4

up vote 9 down vote accepted

You can think of a function like this, with some error check to add

common_prefix() {
  local n=0
  while [[ "${1:n:1}" == "${2:n:1}" ]]; do
    ((n++))
  done
  echo "${1:0:n}"
}
share|improve this answer
    
+1 Nice and clean bash! –  rozcietrzewiacz Aug 7 '11 at 16:08
    
I just noticed that when run with two empty/null args it enters an ∞ loop. [[ -z "$1$2" ]] && return fixes it. –  Peter.O Feb 14 '12 at 14:28
    
This method is exponentially slower (rather than linearly). As the string doubles in length, the time increases by a factor of 4 (approx). Here are some string-length/time comparisons to Gilles' binary-split: .. 64 0m0.005s vs 0m0.003s - 128 0m0.013s vs 0m0.003s - 256 0m0.041s vs 0m0.003s - 512 0m0.143s vs 0m0.005s - 1024 0m0.421s vs 0m0.009s - 2048 0m1.575s vs 0m0.012s - 4096 0m5.967s vs 0m0.022s - 8192 0m24.693s vs 0m0.049s - 16384 1m34.004s vs 0m0.085s - 32768 6m34.721s vs 0m0.168s - 65536 27m34.012s vs 0m0.370s –  Peter.O Aug 29 '12 at 6:15
1  
@Peter.O Quadratically, not exponentially. –  Gilles Aug 29 '12 at 11:27

This can be done entirely inside bash. Although doing string manipulation in a loop in bash is slow, there is a simple algorithm that is logarithmic in the number of shell operations, so pure bash is a viable option even for long strings.

longest_common_prefix () {
  local prefix= n
  ## Truncate the two strings to the minimum of their lengths
  if [[ ${#1} -gt ${#2} ]]; then
    set -- "${1:0:${#2}}" "$2"
  else
    set -- "$1" "${2:0:${#1}}"
  fi
  ## Binary search for the first differing character, accumulating the common prefix
  while [[ ${#1} -gt 1 ]]; do
    n=$(((${#1}+1)/2))
    if [[ ${1:0:$n} == ${2:0:$n} ]]; then
      prefix=$prefix${1:0:$n}
      set -- "${1:$n}" "${2:$n}"
    else
      set -- "${1:0:$n}" "${2:0:$n}"
    fi
  done
  ## Add the one remaining character, if common
  if [[ $1 = $2 ]]; then prefix=$prefix$1; fi
  printf %s "$prefix"
}

The standard toolbox includes cmp to compare binary files. By default, it indicates the byte offset of the first differing bytes. There is a special case when one string is a prefix of the other: cmp produces a different message on STDERR; an easy way to deal with this is to take whichever string is the shortest.

longest_common_prefix () {
  local LC_ALL=C offset prefix
  offset=$(export LC_ALL; cmp <(printf %s "$1") <(printf %s "$2") 2>/dev/null)
  if [[ -n $offset ]]; then
    offset=${offset%,*}; offset=${offset##* }
    prefix=${1:0:$((offset-1))}
  else
    if [[ ${#1} -lt ${#2} ]]; then
      prefix=$1
    else
      prefix=$2
    fi
  fi
  printf %s "$prefix"
}

Note that cmp operates on bytes, but bash's string manipulation operates on characters. This makes a difference in multibyte locales, for examples locales using the UTF-8 character set. The function above prints the longest prefix of a byte string. To handle character strings with this method, we can first convert the strings to a fixed-width encoding. Assuming the locale's character set is a subset of Unicode, UTF-32 fits the bill.

longest_common_prefix () {
  local offset prefix LC_CTYPE="${LC_ALL:=$LC_CTYPE}"
  offset=$(unset LC_ALL; LC_MESSAGES=C cmp <(printf %s "$1" | iconv -t UTF-32) \
                                           <(printf %s "$2" | iconv -t UTF-32) 2>/dev/null)
  if [[ -n $offset ]]; then
    offset=${offset%,*}; offset=${offset##* }
    prefix=${1:0:$((offset/4-1))}
  else
    if [[ ${#1} -lt ${#2} ]]; then
      prefix=$1
    else
      prefix=$2
    fi
  fi
  printf %s "$prefix"
}
share|improve this answer
    
Revisiting this question (1 year on), I've have re-assessed the best answer. It's all quite simple: rock breaks scissors, scissors cut paper, paper wraps rock. and binary eats sequential!.. even for quite short strings.. and as for a moderate 10000 char string being processed sequentially via while char-by-char, I'm still waiting for it as I write this.. time passes.. still waiting (maybe there's something wrong with my system).. time passes.. there must be something wrong; it is only 10,000 itterations! Ah! patience is a virtue (perhaps a curse in this case).. 13m53.755s.. vs, 0m0.322s –  Peter.O Aug 29 '12 at 2:49
    
The 3 methods given here are the outright fastest of all the presented answers.. Basically, cmp is the fastest (but is not char based). The next is iconv and then the very respectibly fast binary-split answer. Thanks Gilles. It took me a year to get to this point, but better late than never. (PS. 2 typo mods in iconv code: $ in =$LC_CTYPE} and \ in UTF-32) \ ) ... PPS. actually the string I mentioned above was longer than 10,000 characters. It was the result of {1..10000} which is, 48,894, but that doesnt' change the differential –  Peter.O Aug 29 '12 at 12:11

In sed, assuming the strings don't contain any newline characters:

string1="test toast"
string2="test test"
printf "%s\n" "$string1" "$string2" | sed -e 'N;s/^\(.*\).*\n\1.*$/\1/'
share|improve this answer
    
But duplicate with this. –  jfgagne Aug 7 '11 at 15:25
    
Brilliant! goes directly to my tips&tricks library :-) –  hmontoliu Aug 8 '11 at 11:27
    
Or, for a bash string, which can't contain \0. Using tr and \0, the method can handle newlines in the string, .... { printf "%s" "$string1" |tr \\n \\0; echo; printf "%s" "$string2" |tr \\n \\0; echo; } | sed -e 'N;s/^\(.*\).*\n\1.*$/\1/' |tr \\0 \\n –  Peter.O Aug 29 '12 at 1:25
    
I've just tested this sed method a bit further,and it seems that using back-references this way (in the search pattern) is hugely expensive. It still outperforms the sequential byte-by-byte looping (by approx a factor of 3), but here is an example: for two 32kb strings (with the last byte being different), it takes 2m4.880s, as compared to Gilles' binary-split method 0m0.168s –  Peter.O Aug 29 '12 at 7:54

This seems crude to me, but you can do it via brute force:

#!/bin/bash

string1="test toast"
string2="test test"

L=1  # Prefix length

while [[ ${string1:0:$L} == ${string2:0:$L} ]]
do
    ((L = L + 1))
done

echo Overlap: ${string1:0:$((L - 1))}

I want some clever algorithm to exist, but I can't find any with a short search.

share|improve this answer
2  
compare half and repeat is n*log(n) rather than n^2. –  Gilles Aug 13 '11 at 21:57
1  
For general reference, it is a bit on the slow side. Two 32768 character strings (the last char being different) took 6m27.689s. –  Peter.O Aug 29 '12 at 8:34
    
Thank you, Peter O. Very interesting. –  Bruce Ediger Aug 29 '12 at 12:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.