☰

Как найти слова, которые следуют определенному порядку

tag-icon • tag-icon bash shell-script scripting
Как найти слова, которые следуют определенному порядку

Я пытаюсь написать скрипт (script1.sh), который находит все возможные слова, имея набор букв.

  • Слова должны начинаться с первой буквы в наборе и заканчиваться последней буквой.

  • Буквы слова должны следовать порядку букв в мешанине.

  • Каждую букву в этой мешанине можно использовать несколько раз.

Так что это

./script1.sh "qwertyuytresdftyuiokn"

должен вывести queenи , questionно не "quieten", потому что "e" стоит перед "u" и "i" в беспорядке.

Я пробовал присваивать переменным первую, последнюю и оставшиеся буквы, а затем использовать 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должен появиться по крайней мере один раз в конце. Каждая буква в середине может появиться ноль или более раз, порядок сохраняется.

Обратите внимание, что скрипт глупый. Если вы предоставите ввод с ., [, ]или около того, то вы получите регулярное выражение, выходящее за рамки спецификации. Предоставьте разумный ввод или расширьте скрипт, чтобы проверить его.

Примеры:

$ ./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/wordsслова, которые начинаются с qв примере. grepТаким образом, набор слов для поиска значительно сокращен.

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)

Связанный контент