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:'
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
I thought this sounded 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}"
Output:
Longest common substring: def
