这可以完全在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"
}
喔人,这是很好的看到别人用这种挣扎,以及:d –
@ajreal:提供的功能有相当冗长,不与琴弦的空间工作。无论如何,我的问题是重复的。对不起。将在那里发表评论 –
不是重复的:交叉点需求是不一样的。 – jfg956