Perl - 2个或更多字符串的最长公共前缀？

-1

我怎样才能创建一个Perl子程序，它将采取一个数组，并找到2个或更多元素的最长共同前缀？（串）Perl - 2个或更多字符串的最长公共前缀？

我有这样的代码：

sub longest_common_prefix { 
    $prefix = shift; 
    for (@_) { 
     chop $prefix while (! /^\Q$prefix\E/); 
     } 
    return $prefix; 
}

但是，如果你正在寻找的所有串最长公共前缀它才会起作用。

例如，如果我通过与以下字符串数组：

aaaBGFB 
aaaJJJJ 
jjfkBBB 
aaaHGHG

我希望它返回aaa的答案。

谢谢！

来源

2016-11-05 Gambit2007

会发生什么，如果“j12345”是组合？如果我们添加“bbbb1”和“bbbb2”会怎么样？它是否正在寻找任何两个字符串之间最长的前缀？还是至少有一个共同点的字符串是LCP？ – Schwern

后者，是的，如果不明确，很抱歉。 – Gambit2007

前缀是否可以是'abcd'，还是必须是重复的相同字母，比如'aaa'？ – toolic

一种方法是存储在一个散的信息。在这个例子中，我将散列键设置为每个前缀的长度，并且该值是找到的实际前缀。

注意，此方法将覆盖键和值是否相同长度的前缀存在，所以你总能获得发现的最长的最后前缀（sort()需要找到一个最长的护理）。

正则表达式说：“找到字符串中的第一个字符，并占领它，并使用第二捕获发现炭，并采集居然有”。这个字符串然后被join()编成一个标量并放入散列。

use warnings; 
use strict; 

my %prefixes; 

while (<DATA>){ 
    my $prefix = join '', /^(.)(\1+)/; 
    $prefixes{length $prefix} = $prefix; 
} 

my $longest = (sort {$b <=> $a} keys %prefixes)[0]; 
print "$prefixes{$longest}\n"; 

__DATA__ 
aaBGFB 
aaaJJJJ 
jjfkBBB 
aaaHGHG

输出：

aaa

来源

2016-11-05 17:31:31 stevieb

伟大的，非常感谢！ – Gambit2007

因qw（abcd abce xxy xxz）'失败。（打印'xx'而不是'abc'。） – ikegami

这仅适用于运行相同字母的前缀。例如，如果你有'（aaBGFB，aaaJJJJ，interspecies，interstellar）'，最长的公共前缀是'inter' – dawg

我会使用修改trie。

通常情况下，人们可以使用以下方法来添加到特里：

sub add { 
    my $p = \shift; 
    my $s = shift; 
    $p = \($$p->{$_}) for split(//, $s); 
    $$p->{''} = 1; 
}

但我们需要两处修改：

字符串的所有前缀必须添加一个字符串时添加。例如，添加abc还应该添加a和ab到线索。
当添加到线索，我们要返回的路径的先前存在的部分的长度。

因此，我们需要：

sub add { 
    my $p = \shift; 
    my $s = shift; 

    my $cp_len = 0; 
    for (split(//, $s)) { 
     $p = \($$p->{$_}); 
     ++$cp_len if $$p->{$_}{''}; 
     $$p->{''} = 1; 
    } 

    return $cp_len; 
}

结合（优化版本），这与一个算法来找到一个列表并且用算法最长的字符串从列表中删除重复的字符串来获得下列溶液：

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

sub add { 
    my $p = \shift; 
    my $s = shift; 

    my $cp_len = 0; 
    for (split(//, $s)) { 
     ++$cp_len if exists($$p->{$_}); 
     $p = \($$p->{$_}); 
    } 

    return $cp_len; 
} 

my $t; 
my $lcp_len = 0; # lcp = longest common prefix 
my %lcps; 
while (<>) { 
    chomp; 
    my $cp_len = add($t, $_) 
     or next; 

    if ($cp_len >= $lcp_len) { 
     if ($cp_len > $lcp_len) { 
     $lcp_len = $cp_len; 
     %lcps =(); 
     } 

     $lcps{ substr($_, 0, $cp_len) } = 1; 
    } 
} 

my @lcps = sort keys %lcps; 

if (@lcps) { 
    say "Longest common prefix(es): @lcps"; 
} else { 
    say "No common prefix"; 
}

数据：

abc 
abc 
abcd 
abcde 
hijklx 
hijkly 
mnopqx 
mnopqy

输出：

Longest common prefix(es): hijkl mnopq

由上述所花费的时间正比于输入字符的数目。

来源

2016-11-05 21:11:56 ikegami

这是'正确'的答案。 – dawg

您可以保留由第一个字符键入的单词数组的散列。根据定义，如果您的单词以相同的字母开头，那么这些单词至少会共享该字母的一个字符通用前缀。

use strict; use warnings; 
sub lcp { 
    (join("\0", @_) =~ /^ ([^\0]*) [^\0]* (?:\0 \1 [^\0]*)* $/sx)[0]; 
} 

my %HoA; 
my $longest=''; 

while (my $line=<DATA>){ 
    $line =~ s/^\s+|\s+$//g ; 
    push @{ $HoA{substr $line, 0, 1} }, $line if $line=~/^[a-zA-Z]/; 
} 

for my $key (sort (keys %HoA)) { 
    if (scalar @{ $HoA{$key} } > 1){ 
     my $lon=lcp(@{ $HoA{$key} }); 
     my $s = join ', ', map { qq/"$_"/ } @{ $HoA{$key} }; 
     print "lcp: \"$lon\" for ($s)\n"; 
     if (length($lon) > length($longest)) { 
      $longest=$lon; 
     }    
    } 
    else{ 
     print "$key: no common prefix\n"; 
    } 
} 
print "\nlongest common prefix is \"$longest\"\n"; 

__DATA__ 
aardvark 
aaaBGFB 
aaaJJJJ 
jjfkBBB 
aaaHGHG 
interspecies 
interstellar 
interstate

打印：然后通过字符通过哈希步进减少对单一最长前缀

lcp: "aa" for ("aardvark", "aaaBGFB", "aaaJJJJ", "aaaHGHG") 
lcp: "inters" for ("interspecies", "interstellar", "interstate") 
j: no common prefix 

longest common prefix is "inters"

来源

2016-11-05 22:52:10 dawg

Perl - 2个或更多字符串的最长公共前缀？

回答

相关问题