두 개의 문자열이 있습니다. 예를 들어 다음과 같이 설정됩니다.
string1="test toast"
string2="test test"
내가 원하는 것은 문자열의 시작 부분부터 겹치는 부분을 찾는 것입니다. 중복이란 위의 예에서 문자열 "test t"를 참조하는 것입니다.
# I look for the command
command "$string1" "$string2"
# that outputs:
"test t"
문자열이 있으면 string1="atest toast"; string2="test test"
검사가 시작 부분에서 시작되고 "a"가 시작 부분에 있으므로 겹치지 않습니다 string1
.
답변1
오류 검사를 추가하여 이와 같은 기능을 생각할 수 있습니다.
common_prefix() {
local n=0
while [[ "${1:n:1}" == "${2:n:1}" ]]; do
((n++))
done
echo "${1:0:n}"
}
답변2
이는 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 문자 집합을 사용하는 것과 같은 멀티바이트 로케일에서는 다릅니다. 위 함수는 바이트 문자열의 가장 긴 접두사를 인쇄합니다. 이런 방식으로 문자열을 처리하려면 먼저 문자열을 고정 너비 인코딩으로 변환해야 합니다. 로케일의 문자 집합이 유니코드의 하위 집합이라고 가정하면 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"
}
답변3
sed에서 문자열에 개행 문자가 포함되어 있지 않다고 가정합니다.
string1="test toast"
string2="test test"
printf "%s\n" "$string1" "$string2" | sed -e 'N;s/^\(.*\).*\n\1.*$/\1/'
답변4
이것은 나에게 조잡해 보이지만 무차별 대입을 통해 이를 수행할 수 있습니다.
#!/bin/bash
string1="test toast"
string2="test test"
L=1 # Prefix length
while [[ ${string1:0:$L} == ${string2:0:$L} ]]
do
((L = L + 1))
done
echo Overlap: ${string1:0:$((L - 1))}
영리한 알고리즘이 존재하기를 바라지만 간단한 검색으로는 찾을 수 없습니다.