Tiền tố chung dài nhất của hai chuỗi trong bash

Question

Tôi có hai chuỗi. Vì lợi ích của ví dụ, chúng được đặt như sau:

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

Điều tôi muốn là tìm chồng chéo bắt đầu ở đầu chuỗi. Với chồng chéo tôi có nghĩa là chuỗi "test t" trong ví dụ trên của tôi.

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

Nếu chuỗi đã string1="atest toast"; string2="test test" họ sẽ không có sự chồng chéo kể từ ngày séc bắt đầu hình thành đầu và "a" vào đầu string1.

Answer 1

Trong sed, giả sử các chuỗi không chứa bất kỳ ký tự newline:

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

Answer 2

Người đàn ông, điều này thật khó khăn. Đó là một nhiệm vụ cực kỳ tầm thường, nhưng tôi không biết làm thế nào để làm điều này với vỏ :)

đây là một giải pháp xấu xí:

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

Answer 3

Có lẽ đơn giản bằng ngôn ngữ khác. Đây là giải pháp của tôi:

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

Nếu đây không phải là một lớp lót, tôi sẽ sử dụng tên biến dài hơn, khoảng trắng, dấu ngoặc ôm, v.v. Tôi cũng chắc chắn có cách nhanh hơn, ngay cả trong perl , nhưng, một lần nữa, đó là một sự cân bằng giữa tốc độ và không gian: điều này sử dụng ít không gian hơn trên những gì đã là một lớp lót dài.

Answer 4

Ok, trong 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}" 

Đó là thuật toán tương tự như trong các ngôn ngữ khác, nhưng chức năng bash tinh khiết. Và, tôi có thể nói, một chút xấu xí, quá :-)

Answer 5

Without sed, sử dụng tiện ích CMP để có được chỉ số của ký tự khác thứ 1 và sử dụng quá trình thay thế để nhận 2 chuỗi thành 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 6

Điều này có thể được thực hiện hoàn toàn bên trong. Mặc dù thực hiện thao tác chuỗi trong một vòng lặp trong bash là chậm, có một thuật toán đơn giản là lôgarit trong số hoạt động của vỏ, vì vậy bash thuần túy là một lựa chọn khả thi ngay cả đối với các chuỗi dài.

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

Hộp công cụ tiêu chuẩn bao gồm cmp để so sánh tệp nhị phân. Theo mặc định, nó cho biết độ lệch byte của các byte khác nhau đầu tiên. Có một trường hợp đặc biệt khi một chuỗi là tiền tố của một chuỗi khác: cmp tạo một thông báo khác trên STDERR; một cách dễ dàng để giải quyết vấn đề này là lấy chuỗi nào ngắn nhất.

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

Lưu ý rằng cmp hoạt động trên byte, nhưng thao tác chuỗi của bash hoạt động trên ký tự. Điều này tạo nên sự khác biệt về miền địa phương nhiều byte, ví dụ cho các miền địa phương bằng cách sử dụng bộ ký tự UTF-8. Hàm trên in ra tiền tố dài nhất của chuỗi byte. Để xử lý các chuỗi ký tự bằng phương thức này, trước tiên chúng ta có thể chuyển đổi các chuỗi thành mã hóa có độ rộng cố định. Giả sử bộ ký tự của miền địa phương là một tập con của Unicode, UTF-32 phù hợp với hóa đơn.

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 7

Chỉ là một cách khác bằng cách sử dụng 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 8

Một phiên bản cải tiến của ví dụ sed, điều này thấy tiền tố chung của N chuỗi (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' 

Nếu chuỗi được lưu trữ trong một mảng, họ có thể được đường ống để sed với printf:

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

Bạn cũng có thể sử dụng một 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[*]}") 

Chuỗi tại đây (giống như tất cả các chuyển hướng) có thể đi bất cứ đâu trong một lệnh đơn giản.

Answer 9

Grep biến thể ngắn (ý tưởng vay mượn từ sed một):

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

Giả chuỗi không có ký tự dòng mới. Nhưng dễ dàng có thể được điều chỉnh để sử dụng bất kỳ dấu phân cách nào.

Cập nhật lúc 2016/10/24: Trên các phiên bản hiện đại của grep bạn có thể nhận phàn nàn grep: unescaped^or $ not supported with -Pz, chỉ cần sử dụng \A thay vì ^:

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

Answer 10

Tuy nhiên, biến thể khác, sử dụng GNU grep:

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

Answer 11

Nếu sử dụng các ngôn ngữ khác, làm thế nào về 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 đến @RickardSjogren's answer to stack overflow 18715688)