Bash is the longest common part of two lines

Question

I have the following lines: "abcdefx", "zzdefghij" I would like to extract the common part of the two lines, i.e. Here is the "def". I tried with sed, but I could not do this if the common part was not a prefix:

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

Answer 1

I thought this sounds interesting, here is my solution:

first="abcdefx"
second="zzdefghij"

for i in $(seq ${#first} -1 1); do
    for j in $(seq 0 $((${#first}-i))); do
        grep -q "${first:$j:$i}" <<< "$second" && match="${first:$j:$i}" && break 2
    done
done

echo "Longest common substring: ${match:-None found}"

Conclusion:

Longest common substring: def

Answer 2

This pure bash script will find the first longest substring of its two arguments in a rather 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