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

Ответ 1

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

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

Ответ 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'

Если строки хранятся в массиве, они могут быть отправлены с помощью printf:

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

Вы также можете использовать here-string:

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[*]}")

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

Ответ 3

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

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

Ответ 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"
}

Ответ 5

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

$ 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

Ответ 6

Это, вероятно, проще на другом языке. Здесь мое решение:

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

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

Ответ 7

Без 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))}

Ответ 8

Хорошо, в 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. И, могу ли я сказать, немного уродливый тоже: -)

Ответ 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

Ответ 10

Человек, это сложно. Это чрезвычайно тривиальная задача, но я не знаю, как это сделать с оболочкой:)

вот уродливое решение:

echo "$2" | awk 'BEGIN{FS=""} { n=0; while(n<=NF) {if ($n == substr(test,n,1)) {printf("%c",$n);} n++;} print ""}' test="$1"

Ответ 11

Если вы используете другие языки, как насчет python:

cmnstr() { python -c "from difflib import SequenceMatcher
s1, s2 = ('''$1''', '''$2''')
m = SequenceMatcher(None,s1,s2).find_longest_match(0,len(s1),0,len(s2))
if m.a == 0: print(s1[m.a: m.a+m.size])"
}
$ cmnstr x y
$ cmnstr asdfas asd
asd

(h/t to @RickardSjogren ответ на переполнение стека 18715688)