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);

Вывод, конечно, такой же, как и в предыдущем коде