¿Cómo encuentro la superposición de dos cadenas en bash? [cerrado]

Tengo dos cuerdas Por el bien del ejemplo, se establecen así:

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

Lo que quiero es encontrar la superposición que comienza en el comienzo de las cadenas. Con superposición me refiero a la cadena "prueba t" en mi ejemplo anterior.

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

Si las cadenas estuvieran, string1="atest toast"; string2="test test"no tendrían superposición ya que el cheque comienza desde el principio y la "a" al comienzo de string1.

Puede pensar en una función como esta, con alguna verificación de error para agregar

common_prefix() {
  local n=0
  while [[ "${1:n:1}" == "${2:n:1}" ]]; do
    ((n++))
  done
  echo "${1:0:n}"
}

Esto se puede hacer completamente dentro de bash. Si bien la manipulación de cadenas en un bucle en bash es lenta, existe un algoritmo simple que es logarítmico en la cantidad de operaciones de shell, por lo que bash puro es una opción viable incluso para cadenas largas.

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"
}

La caja de herramientas estándar incluye cmppara comparar archivos binarios. Por defecto, indica el desplazamiento de bytes de los primeros bytes diferentes. Hay un caso especial cuando una cadena es un prefijo de la otra: cmpproduce un mensaje diferente en STDERR; Una manera fácil de lidiar con esto es tomar la cadena que sea más corta.

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"
}

Tenga en cuenta que cmpopera en bytes, pero la manipulación de cadenas de bash funciona en caracteres. Esto marca la diferencia en configuraciones regionales de varios bytes, por ejemplo, configuraciones regionales que utilizan el juego de caracteres UTF-8. La función anterior imprime el prefijo más largo de una cadena de bytes. Para manejar cadenas de caracteres con este método, primero podemos convertir las cadenas a una codificación de ancho fijo. Suponiendo que el conjunto de caracteres de la configuración regional es un subconjunto de Unicode, UTF-32 se ajusta a la factura.

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"
}

En sed, suponiendo que las cadenas no contienen ningún carácter de nueva línea:

string1="test toast"
string2="test test"
printf "%s\n" "$string1" "$string2" | sed -e 'N;s/^\(.*\).*\n\1.*$/\1/'

Esto me parece crudo, pero puedes hacerlo a través de la fuerza bruta:

#!/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))}

Quiero que exista algún algoritmo inteligente, pero no puedo encontrar ninguno con una búsqueda corta.