☰

특정 순서를 따르는 단어를 찾는 방법

tag-icon • tag-icon bash shell-script scripting
특정 순서를 따르는 단어를 찾는 방법

나는 뒤죽박죽된 문자가 주어졌을 때 가능한 모든 단어를 찾는 스크립트(script1.sh)를 작성하려고 합니다.

  • 단어는 뒤죽박죽의 첫 글자로 시작하고 마지막 글자로 끝나야 합니다.

  • 단어의 글자는 뒤죽박죽의 글자 순서를 따라야 합니다.

  • 뒤죽박죽의 각 문자는 두 번 이상 사용할 수 있습니다.

그래서 이거

./script1.sh "qwertyuytresdftyuiokn"

"e"가 뒤죽박죽에서 "u"와 "i" 앞에 오기 때문에 출력해야 queen하지만 "quieten"해서는 안 됩니다.question

첫 번째, 마지막 및 나머지 문자를 변수에 할당한 다음 egrep을 사용하여 단어를 찾으려고 시도했지만 문자 순서를 사용하는 방법을 찾을 수 없습니다. 그래서 이것은 나에게도 잘못된 단어를 제공합니다.

#!/bin/bash

first_letter=$(echo $@ | cut -c1)
last_letter=$(echo $@ |rev| cut -c1)
remaining_letters=$(echo $@ | cut -c2- | rev | cut -c2-)

grep -E "^$first_letter[$remaining_letters]*$last_letter$" /usr/share/dict/words

그런 다음 뒤죽박죽을 배열로 바꾸려고 시도했지만 뒤죽박죽의 순서를 따르는 단어를 찾는 방법을 다시 찾을 수 없었습니다.

답변1

#!/bin/sh
pttrn="^$(printf '%s' "$1" | sed -e 's/\(.\)/\1*/g' -e 's/\*/\\+/' -e 's/\*$/\\+/')"'$'
grep "$pttrn" /usr/share/dict/words

*각 문자 뒤에 삽입하여 첫 번째 인수에서 패턴을 얻습니다 . 그런 다음 첫 번째 *는 \+; 마지막도 마찬가지다 *. 추가적으로 ^및 $추가됩니다. 예제 입력은 다음 패턴을 생성합니다.

^q\+w*e*r*t*y*u*y*t*r*e*s*d*f*t*y*u*i*o*k*n\+$

이 패턴은 에 적합한 패턴입니다 grep. q시작 부분에 한 번 이상 나타나야 하고 n끝 부분에도 한 번 이상 나타나야 합니다. 중간에 있는 각 문자는 0번 이상 나타날 수 있으며 순서가 유지됩니다.

스크립트가 멍청하다는 점에 유의하세요. ., 등으로 입력을 제공하면 사양을 넘어서는 정규식을 얻게 [됩니다 . ]올바른 입력을 제공하거나 스크립트를 확장하여 유효성을 검사하세요.

예:

$ ./script1.sh qwertyuytresdftyuiokn
queen
question
$ ./script1.sh te
tee
$ ./script1.sh superuser
seer
serer
spur
super
supper
surer
$

답변2

여기에 접근하는 한 가지 방법이 있습니다.

먼저, 뒤죽박죽과 동일한 문자로 시작하고 끝나는 단어로 단어 목록을 필터링합니다. 예를 들어, 뒤죽박죽이 위치 매개변수로 전달되는 경우 $1(최근 쉘을 가정 bash)

grep -x "${1:0:1}.*${1:(-1):1}" /usr/share/dict/words

그런 다음 이 단어 각각을 정규 표현식으로 분해하세요. "좋은" 방법은 생각나지 않지만, 예를 들어 GNU sed를 사용하면 할 수 있습니다.

$ sed -E 's/(.)\1*/+.*\1/2g' <<< "queen"
q+.*u+.*e+.*n

이제 생성된 각 패턴에 대해 뒤죽박죽을 테스트합니다.

함께 모아서:

$ cat script1 
#!/bin/bash

wordlist=/usr/share/dict/words

while IFS= read -r word; do 
  grep -qEx "$(sed -E 's/(.)\1*/+.*\1/2g' <<< "$word")" <<< "$1" && printf '%s\n' "$word"
done < <(grep -x "${1:0:1}.*${1:(-1):1}" "$wordlist")

그 다음에

$ ./script1 qwertyuytresdftyuiokn
queen
question

답변3

여기에 또 다른 코드가 있습니다( 에서 실행 bash). python코드는 정규식을 생성하고 이를 에 제공합니다 grep. 그런 다음 이진 검색을 수행하여 예제에서 시작하는 모든 단어를 가져오는 grep유서 깊은 유틸리티의 출력에 대해 작업합니다 . 따라서 검색할 단어 집합이 크게 줄어듭니다.look/usr/share/dict/wordsqgrep

python3 -c 'import sys
arr = list(sys.argv[1])
print(*arr, sep="*")
' $1 | grep -x -f - <(look ${1:0:1})

또는 정규식을 피하는 look+ 솔루션python3

look q | ./finder.py "qwertyuytresdftyuiokn"

어디에 finder.py다음과 같습니다 :

#!/usr/bin/env python3
import sys
from itertools import groupby

seek_word = sys.argv[1]
for word in sys.stdin:
    orig_word = word.strip()
    word = ''.join(k for k, g in groupby(orig_word)) 
    s_w = iter(seek_word)
    i_word = iter(word)
    if all(c in s_w for c in i_word) and not next(s_w, None):
        print(orig_word)

관련 정보