特定の順序に従う単語を見つける方法

特定の順序に従う単語を見つける方法

私は複数の文字が与えられたときに可能なすべての単語を見つけることができるスクリプト(script1.sh)を書こうとしています。

  • 言葉はパブの最初の文字で始まり、最後の文字で終わらなければなりません。

  • 単語の文字は、パブの文字の順序に従う必要があります。

  • 混乱の各文字は複数回使用できます。

だからこれ

./script1.sh "qwertyuytresdftyuiokn"

出力する必要がqueenありますが、question「e」が「u」と「i」の前に混同されて現れるので、「quieten」してはいけません。

最初、最後、および残りの文字を変数に割り当ててから、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\+$

これは正しいパターンですgrepq開始は少なくとも1回は発生し、n終了は少なくとも1回発生する必要があります。中央の各文字は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)は次のとおりです。次に、古代ユーティリティの出力が処理され、バイナリ検索が実行され、例で始まるすべての単語が取得されます。したがって、検索する単語のセットが大幅に減少します。pythongrepgreplook/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)

関連情報