perl - Perl: 最長の接頭辞一致を行う最良の方法 (文字列)

Question

私は約5000語のリストを持っています。特定の単語のそれらの単語の中で最長のプレフィックスマッチを見つけたいです。たとえば、私のリストには次のものがあります。

1
121
12234
20345
21345

ここで 12134 を検索すると、結果は 121 (最長一致) になります。私はそれがさまざまな方法でできることを知っています。しかし、最も効率的な方法は何ですか？

Answer 1

#!/usr/bin/env perl

use strict;
use warnings;

my @prefixes = qw(
    1
    121
    12234
    20345
    21345
);

my $num = '12134';

my ($longest) = sort { length $b <=> length $a } grep { 0 == index $num, $_ } @prefixes;

print "$longest\n";

出力

121

Answer 2

正規表現エンジンにこれを実行させることができます。とても速いはずです

正規表現パターンを一度だけ構築する必要があり、その後、任意の数のターゲット文字列の最長プレフィックスを見つけるために使用できることが明らかであることを願っています

use strict;
use warnings;
use 5.010;

my @prefixes = qw/
    1
    121
    12234
    20345
    21345
/;

my $target = 12134;

my $re = join '|', sort { length $b <=> length $a } @prefixes;
$re = qr/(?:$re)/;

say $1 if $target =~ /^($re)/;

出力

121

---

アップデート

または、このTree::Trieモジュールを使用して、正規表現エンジンが提供するトライ検索を次のように実装できます。

use strict;
use warnings;
use 5.010;

use Tree::Trie;

my @prefixes = qw/
    1
    121
    12234
    20345
    21345
/;

my $target = 12134;

my $trie = Tree::Trie->new({ deepsearch => 'prefix' });
$trie->add(@prefixes);

say scalar $trie->lookup($target);

もちろん、出力は前のコードと同じです