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'

如果字符串存储在数组中,则可以使用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[*]}")

here-string(与所有重定向一样)可以在简单命令中的任何位置.

Answer 3

另一个变种,使用GNU grep:

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

Answer 4

这可以完全在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 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

好的，在 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 7

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