Самый длинный общий префикс двух строк в bash

Question

У меня есть две строки.Для примера они установлены так:

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

Я хочу найти перекрытие, начинающееся в начале строк.Под перекрытием я подразумеваю строку «test t» в моем примере выше.

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

Если бы строки были string1="atest toast"; string2="test test", они не имели бы перекрытия, так как проверка начинается с начала, а «a» вначало string1.

Answer 1

В sed, при условии, что строки не содержат символов новой строки:

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

Answer 2

Улучшенная версия примера sed. Здесь находит общий префикс N строк (N> = 0):

string1="test toast"
string2="test test"
string3="teaser"
{ echo "$string1"; echo "$string2"; echo "$string3"; } | sed -e 'N;s/^\(.*\).*\n\1.*$/\1\n\1/;D'

Если строки хранятся в массиве, их можно передать в sedс printf :

strings=("test toast" "test test" "teaser")
printf "%s\n" "${strings[@]}" | sed -e '$!{N;s/^\(.*\).*\n\1.*$/\1\n\1/;D;}'

Вы также можете использовать здесь-строку :

strings=("test toast" "test test" "teaser")
oIFS=$IFS
IFS=$'\n'
<<<"${strings[*]}" sed -e '$!{N;s/^\(.*\).*\n\1.*$/\1\n\1/;D;}'
IFS=$oIFS
# for a local IFS:
(IFS=$'\n'; sed -e '$!{N;s/^\(.*\).*\n\1.*$/\1\n\1/;D;}' <<<"${strings[*]}")

Здесь-строка (как со всемиперенаправления) может идти куда угодно в пределах простой команды.

Answer 3

Еще один вариант, использующий GNU grep:

$ string1="test toast"
$ string2="test test"
$ grep -zPo '(.*).*\n\K\1' <<< "$string1"$'\n'"$string2"
test t

Answer 4

Это можно сделать полностью внутри bash.Хотя манипулирование строками в цикле в bash является медленным, существует простой алгоритм, логарифмирующий по количеству операций оболочки, поэтому чистый bash является приемлемым вариантом даже для длинных строк.

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

СтандартПанель инструментов включает cmp для сравнения двоичных файлов.По умолчанию, это указывает смещение байта первых отличающихся байтов.Существует особый случай, когда одна строка является префиксом другой: cmp создает другое сообщение в STDERR;простой способ справиться с этим - взять самую короткую строку.

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

Обратите внимание, что cmp работает с байтами, но манипулирование строками в bash работает с символами.Это имеет значение для многобайтовых локалей, например, для локалей, использующих набор символов UTF-8.Функция выше печатает самый длинный префикс байтовой строки.Чтобы обработать строки символов с помощью этого метода, мы можем сначала преобразовать строки в кодировку с фиксированной шириной.Предполагая, что набор символов локали является подмножеством Unicode, UTF-32 отвечает всем требованиям.

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

Answer 5

Grep короткий вариант (идея заимствована из sed):

$ echo -e "String1\nString2" | grep -zoP '^(.*)(?=.*?\n\1)'
String

Предполагается, что строка не имеет символа новой строки. Но легко можно настроить на использование любого разделителя.

Обновление от 2016-10-24: в современных версиях grep вы можете получать жалобы grep: unescaped ^ or $ not supported with -Pz, просто используйте \A вместо ^:

$ echo -e "String1\nString2" | grep -zoP '\A(.*)(?=.*?\n\1)'
String

Answer 6

Без sed, используя утилиту cmp для получения индекса 1-го другого символа, и используя подстановку процесса для получения 2 строк в cmp:

string1="test toast"
string2="test test"
first_diff_char=$(cmp <( echo "$string1" ) <( echo "$string2" ) | cut -d " " -f 5 | tr -d ",")
echo ${string1:0:$((first_diff_char-1))}

Answer 7

Наверное, проще на другом языке.Вот мое решение:

common_bit=$(perl -le '($s,$t)=@ARGV;for(split//,$s){last unless $t=~/^\Q$z$_/;$z.=$_}print $z' "$string1" "$string2")

Если бы это не было одной строкой, я бы использовал более длинные имена переменных, больше пробелов, больше скобок и т. Д. Я также уверен, что есть более быстрый способ, дажев perl, но, опять же, это компромисс между скоростью и пространством: он использует меньше места на длинном однострочнике.

Answer 8

Если у вас есть возможность установить пакет Python, вы можете использовать эту утилиту Python

# install pythonp
pythonp -m pip install pythonp

echo -e "$string1\n$string2" | pythonp 'l1,l2=lines
res=itertools.takewhile(lambda a: a[0]==a[1], zip(l1,l2)); "".join(r[0] for r in res)'

Answer 9

Просто еще один способ использовать только Bash.

string1="test toast"
string2="test test"
len=${#string1}

for ((i=0; i<len; i++)); do
   if [[ "${string1:i:1}" == "${string2:i:1}" ]]; then
      continue
   else
      echo "${string1:0:i}"                       
      i=len
   fi
done

Answer 10

Хорошо, в bash:

#!/bin/bash

s="$1"
t="$2"
l=1

while [ "${t#${s:0:$l}}" != "$t" ]
do
  (( l = l + 1 ))
done
(( l = l - 1 ))

echo "${s:0:$l}"

Это тот же алгоритм, что и в других языках, но чисто функциональность bash. И, я бы сказал, немного уродливее: -)