4

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:'
user1850133
  • 2,833
  • 9
  • 29
  • 39
  • 5
    This is not a trivial problem even using a real programming language. – stark Apr 25 '14 at 14:15
  • What is the use case? This sounds like homework or idle curiosity. – l0b0 Apr 25 '14 at 14:25
  • I have files which I would like to classify following their base name into directories. The problem is that for one given base there could be files with some prefix separated with '-' or '\_' and zero, one, three, or four trailing substrings separated with '-', '\_', or even nothing. the only way to determine the base name for files of a given base is to extract the common part of the file names. – user1850133 Apr 25 '14 at 14:43
  • You might want to check out http://rosettacode.org/wiki/Longest_common_subsequence -- some solutions for a similar problem in various languages. – glenn jackman Apr 25 '14 at 15:01
  • 1
    (saying the obvious) ... and you have no opportunity to reorganize the generating system to create something that can be parsed more easily? Good luck. – shellter Apr 25 '14 at 15:05
  • A possible duplicate of [Longest common prefix of two strings in bash](https://stackoverflow.com/questions/6973088/longest-common-prefix-of-two-strings-in-bash) – Wiktor Stribiżew Nov 27 '19 at 08:37

2 Answers2

6

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
gniourf_gniourf
  • 44,650
  • 9
  • 93
  • 104
4

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
Josh Jolly
  • 11,258
  • 2
  • 39
  • 55