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"他们将有没有重叠，因为检查开始形成之初，“一”在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

男人，这很难。这是一个非常简单的任务，但我不知道如何与外壳做到这一点:)

这里是一个丑陋的解决方案：

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

这也可能是另一种语言简单。这里是我的解决方案：

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

如果这不是一个衬垫，我会使用更长的变量名，更多的空白，多个支架，等我也肯定有一个更快的方法，甚至在Perl ，但是，它又是速度和空间之间的折衷：这在已经很长的单线上使用更少的空间。

Answer 4

好了，在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的功能。而且，我可以说，有点丑陋，太:-)

Answer 5

没有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))} 

Answer 6

这可以完全在bash中完成。尽管在bash循环中执行字符串操作很慢，但有一个简单的算法在shell操作的数量上是对数的，所以即使对于长字符串，纯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 7

只是又一种使用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

的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到sed的：

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

这里的字符串（与所有重定向一样）可以在任何地方使用简单的命令。

Answer 9

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 10

另一种变型，使用GNU的grep：

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

Answer 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到@RickardSjogren's answer to stack overflow 18715688）