¿Cómo encuentro la superposition de dos cadenas en bash?

Tengo dos strings. Por el bien del ejemplo, se configuran así:

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

Lo que quiero es encontrar la superposition comenzando al comienzo de las cadenas. Con superposition me refiero a la cadena "test t" en mi ejemplo anterior.

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

Si las cadenas fueran string1="atest toast"; string2="test test" string1="atest toast"; string2="test test" no se superpondrían ya que la comprobación comienza desde el principio y la "a" al comienzo de la string1 .

Puedes pensar en una function como esta, con alguna comprobació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. Aunque la manipulación de cadenas en un bucle en bash es lenta, existe un algorithm simple que es logarítmico en el número de operaciones de shell, por lo que pure bash 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 cmp para comparar files binarys. 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: cmp produce un post 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 count que cmp opera en bytes, pero la manipulación de cadenas de bash opera en los caracteres. Esto hace una diferencia en las configuraciones regionales multibyte, por ejemplo las configuraciones regionales que usan el juego de caracteres UTF-8. La function 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 encoding de ancho fijo. Suponiendo que el set de caracteres de la configuration regional es un subset de Unicode, UTF-32 se ajusta a la ley.

 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 caracteres 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 algorithm inteligente, pero no puedo encontrar ninguno con una búsqueda breve.