bash longest common part of two string

Question

I have the following strings: "abcdefx", "zzdefghij" I would like to extract the common part of the two strings, i.e. here "def". I tried with sed but I couldn't do that unless the common part was a prefix like this:

fprint "%s\n%\n" | sed -e 'N;s:\(.*\).*\n\1.*:\1:'

Answer 1

This pure bash script will find the first longest substring of its two arguments, in a fairly efficient way:

#!/bin/bash

if ((${#1}>${#2})); then
   long=$1 short=$2
else
   long=$2 short=$1
fi

lshort=${#short}
score=0
for ((i=0;i<lshort-score;++i)); do
   for ((l=score+1;l<=lshort-i;++l)); do
      sub=${short:i:l}
      [[ $long != *$sub* ]] && break
      subfound=$sub score=$l
   done
done

if ((score)); then
   echo "$subfound"
fi

Demo (I called the script banana):

$ ./banana abcdefx zzdefghij
def
$ ./banana "I have the following strings: abcdefx, zzdefghij I would like to extract the common part of the two strings, i.e. here def." "I tried with sed but I couldn't do that unless the common part was a prefix like this"
 the common part