正则表达式 – 如何使用Perl从一组字母中生成单词列表？

[你已经指定输入中的字母可以多次使用,但我会在这里留下这篇文章以防有人发现它有用.]

有效地做到这一点的关键是对单词中的字母进行排序.

abracadabra => AAAAABBCDRR
abroad      => AABDOR
drab        => ABDR

然后很明显“drab”在“abracadabra”中.

abracadabra => AAAAABBCDRR
drab        => A    B  DR

那“国外”不是.

abracadabra => AAAAABBCD RR
abroad      => AA   B  DOR

我们将排序后的字母称为“签名”.如果您可以从“A”的签名中删除字母以获得“B”的签名,则单词“B”in在单词“A”中.使用正则表达式模式很容易检查.

sig('drab') =~ /^A?A?A?A?A?B?B?C?D?R?R?z/

或者,如果我们为了效率而消除不必要的回溯,我们就会得到

sig('drab') =~ /^A?+A?+A?+A?+A?+B?+B?+C?+D?+R?+R?+z/

既然我们知道我们想要什么样的模式,那只需要构建它.

use strict;
use warnings;
use feature qw( say );

sub sig { join '',sort grep /^pLz/,split //,uc $_[0] }

my $key = shift(@ARGV);

my $pat = sig($key);
$pat =~ s/.K/?+/sg;
my $re = qr/^(?:$pat)z/s;

my $shortest = 9**9**9;
my $longest  = 0;
my $count    = 0;
while (my $word = <>) {
   chomp($word);
   next if !length($word);  # My dictionary starts with a blank line!! 
   next if sig($word) !~ /$re/;
   say $word;
   ++$count;
   $shortest = length($word) if length($word) < $shortest;
   $longest  = length($word) if length($word) > $longest;
}

say "Words:    $count";
if ($count) {
   say "Shortest: $shortest";
   say "Longest:  $longest";
}

例：

$perl script.pl EBLAIDL /usr/share/dict/words
A
Abe
Abel
Al
...
libel
lid
lie
lied

Words:    117
Shortest: 1
Longest:  6