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

Усовершенствованная версия примера 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[*]}")

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

Это можно сделать полностью внутри 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"
}

Без sed, используя утилиту cmp, чтобы получить индекс первого отличного символа, и используя подстановку процесса, чтобы получить 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))}

Если у вас есть возможность установить пакет 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)'

Просто еще один способ использовать только 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

Если вы используете другие языки, как насчет 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 на @ RickardSjogren на переполнение стека 18715688 )

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

вот ужасное решение:

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

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

common_bit=$(perl -le '($s,$t)=@ARGV;for(split//,$s){last unless $t=~/^\Q$z
 Наверное, проще на другом языке. Вот мое решение: 
 [110] 
 Если бы это не было одной строкой, я бы использовал более длинные имена переменных, больше пробелов, больше скобок и т. Д. Я также уверен, что есть более быстрый путь, даже в Perl, но, опять же, это компромисс между скоростью и пространством: он использует меньше места на длинном однострочнике. 
/;$z.=
 Наверное, проще на другом языке. Вот мое решение: 
 [110] 
 Если бы это не было одной строкой, я бы использовал более длинные имена переменных, больше пробелов, больше скобок и т. Д. Я также уверен, что есть более быстрый путь, даже в Perl, но, опять же, это компромисс между скоростью и пространством: он использует меньше места на длинном однострочнике. 
}print $z' "$string1" "$string2")

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

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

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

Короткий вариант 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

Другой основанный на питоне ответ, основанный на собственной функции модуля os.path commonprefix

#!/bin/bash
cat mystream | python -c  
 Longform, это 
 
import sys
import os
sys.stdout.write(
    os.path.commonprefix(sys.stdin.readlines()) + b'\n'
)
 
 
  /! \ Примечание:   весь текст потока будет загружен в память в виде строковых объектов Python, прежде чем будет обработан этим методом  
 
 
 
 Если не требуется буферизация всего потока в памяти, мы можем использовать коммуникативное свойство и проверку общности префиксов между каждой входной парой 
 
$!/bin/bash
cat mystream | python -c  
 Длинная форма 
 
import sys
import os
prefix = None
for line in sys.stdin:
    prefix=os.path.commonprefix(
        [line] + ([prefix] if prev else [])
    )
sys.stdout.write(prefix)
 
 Оба эти метода должны быть бинарно-безопасными, так как в них не требуется ввод / вывод данных для кодирования ascii или utf-8, если вы столкнетесь с ошибками кодирования, python 3 переименуется в sys.stdin в sys.stdin.buffer и sys.stdout в sys.stdout.buffer, который не будет автоматически декодировать / кодировать потоки ввода / вывода при использовании 
import sys\nimport os\nfor line in sys.stdin:\n\tif not os.path.isfile(line.strip()):\n\t\tcontinue\n\tsys.stdout.write(line)\n') | pythoin sys.stdin:\n\tprefix=os.path.commonprefix([line] + ([prefix] if prefix else []))\nsys.stdout.write(prefix)''
 
 Длинная форма 
 
import sys
import os
prefix = None
for line in sys.stdin:
    prefix=os.path.commonprefix(
        [line] + ([prefix] if prev else [])
    )
sys.stdout.write(prefix)
 
 Оба эти метода должны быть бинарно-безопасными, так как в них не требуется ввод / вывод данных для кодирования ascii или utf-8, если вы столкнетесь с ошибками кодирования, python 3 переименуется в sys.stdin в sys.stdin.buffer и sys.stdout в sys.stdout.buffer, который не будет автоматически декодировать / кодировать потоки ввода / вывода при использовании 
import sys, os; sys.stdout.write(os.path.commonprefix(sys.stdin.readlines()) + b\'\\n\')'

Longform, это

import sys
import os
sys.stdout.write(
    os.path.commonprefix(sys.stdin.readlines()) + b'\n'
)

/! \ Примечание: весь текст потока будет загружен в память в виде строковых объектов Python, прежде чем будет обработан этим методом

Если не требуется буферизация всего потока в памяти, мы можем использовать коммуникативное свойство и проверку общности префиксов между каждой входной парой

$!/bin/bash
cat mystream | python -c  
 Длинная форма 
 
import sys
import os
prefix = None
for line in sys.stdin:
    prefix=os.path.commonprefix(
        [line] + ([prefix] if prev else [])
    )
sys.stdout.write(prefix)
 
 Оба эти метода должны быть бинарно-безопасными, так как в них не требуется ввод / вывод данных для кодирования ascii или utf-8, если вы столкнетесь с ошибками кодирования, python 3 переименуется в sys.stdin в sys.stdin.buffer и sys.stdout в sys.stdout.buffer, который не будет автоматически декодировать / кодировать потоки ввода / вывода при использовании 
import sys\nimport os\nfor line in sys.stdin:\n\tif not os.path.isfile(line.strip()):\n\t\tcontinue\n\tsys.stdout.write(line)\n') | pythoin sys.stdin:\n\tprefix=os.path.commonprefix([line] + ([prefix] if prefix else []))\nsys.stdout.write(prefix)''

Длинная форма

import sys
import os
prefix = None
for line in sys.stdin:
    prefix=os.path.commonprefix(
        [line] + ([prefix] if prev else [])
    )
sys.stdout.write(prefix)

Оба эти метода должны быть бинарно-безопасными, так как в них не требуется ввод / вывод данных для кодирования ascii или utf-8, если вы столкнетесь с ошибками кодирования, python 3 переименуется в sys.stdin в sys.stdin.buffer и sys.stdout в sys.stdout.buffer, который не будет автоматически декодировать / кодировать потоки ввода / вывода при использовании