Como encontro a sobreposição de duas strings no bash? [fechadas]

Eu tenho duas cordas. Para fins de exemplo, eles são definidos assim:

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

O que eu quero é encontrar a sobreposição começando no início das strings. Com sobreposição, quero dizer a string "test t" no meu exemplo acima.

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

Se as strings fossem, string1="atest toast"; string2="test test"elas não teriam sobreposição desde que a verificação começa no início e o "a" no início de string1.

Você pode pensar em uma função como esta, com alguma verificação de erro para adicionar

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

Isso pode ser feito inteiramente dentro do bash. Embora a manipulação de strings em um loop no bash seja lenta, existe um algoritmo simples que é logarítmico no número de operações do shell, portanto o bash puro é uma opção viável mesmo para strings longas.

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

A caixa de ferramentas padrão inclui cmppara comparar arquivos binários. Por padrão, indica o deslocamento de bytes dos primeiros bytes diferentes. Há um caso especial quando uma string é um prefixo da outra: cmpproduz uma mensagem diferente em STDERR; uma maneira fácil de lidar com isso é usar a string mais curta.

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

Observe que cmpopera em bytes, mas a manipulação de string do bash opera em caracteres. Isso faz a diferença nos códigos de idioma multibyte, por exemplo, códigos de idioma usando o conjunto de caracteres UTF-8. A função acima imprime o prefixo mais longo de uma sequência de bytes. Para lidar com cadeias de caracteres com esse método, primeiro podemos converter as cadeias de caracteres em uma codificação de largura fixa. Supondo que o conjunto de caracteres do código de idioma seja um subconjunto de Unicode, o UTF-32 se ajusta à conta.

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

No sed, supondo que as strings não contenham caracteres de nova linha:

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

Isso me parece grosseiro, mas você pode fazê-lo através da força 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))}

Quero que exista um algoritmo inteligente, mas não consigo encontrá-lo com uma breve pesquisa.