Comment trouver le chevauchement de deux chaînes dans bash? [fermé]

J'ai deux cordes. Pour les besoins de l'exemple, ils sont définis comme suit:

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

Ce que je veux, c'est trouver le chevauchement à partir du début des chaînes. Avec chevauchement, je veux dire la chaîne "test t" dans mon exemple ci-dessus.

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

Si les chaînes étaient, string1="atest toast"; string2="test test"elles n'auraient aucun chevauchement puisque le contrôle commence au début et le "a" au début de string1.

Vous pouvez penser à une fonction comme celle-ci, avec une vérification des erreurs à ajouter

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

Cela peut être fait entièrement à l'intérieur de bash. Bien que la manipulation de chaînes dans une boucle en bash soit lente, il existe un algorithme simple qui est logarithmique dans le nombre d'opérations du shell, donc bash pur est une option viable même pour les chaînes longues.

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 boîte cmpà outils standard comprend pour comparer les fichiers binaires. Par défaut, il indique le décalage en octets des premiers octets différents. Il existe un cas particulier lorsqu'une chaîne est un préfixe de l'autre: cmpproduit un message différent sur STDERR; un moyen simple de résoudre ce problème consiste à prendre la chaîne la plus courte.

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

Notez que cela cmpfonctionne sur les octets, mais la manipulation des chaînes de bash fonctionne sur les caractères. Cela fait une différence dans les paramètres régionaux multioctets, pour des exemples de paramètres régionaux utilisant le jeu de caractères UTF-8. La fonction ci-dessus affiche le préfixe le plus long d'une chaîne d'octets. Pour gérer les chaînes de caractères avec cette méthode, nous pouvons d'abord convertir les chaînes en un codage à largeur fixe. En supposant que le jeu de caractères des paramètres régionaux est un sous-ensemble d'Unicode, UTF-32 convient parfaitement.

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

Dans sed, en supposant que les chaînes ne contiennent aucun caractère de nouvelle ligne:

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

Cela me semble grossier, mais vous pouvez le faire via la force brute:

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

Je veux qu'un algorithme intelligent existe, mais je n'en trouve pas avec une courte recherche.