我需要找到子串中最长的重复字符串 . 假设我有字符串 "bannana"
维基百科says以下:
在计算机科学中,最长的重复子串问题是找到至少发生两次的字符串的最长子串的问题 . 在带有字符串“ATCGATCGA $”的图中,最长的重复子串是“ATCGA”
所以我假设对于字符串 "bannana"
,有两个同样长的子串(如果不正确我请): "an"
和 "na"
.
维基百科也says为此目的使用后缀树 . 更具体一点here是引用怎么做(这似乎比wikipedia上的定义更明白):
构建一个后缀树,然后找到至少有2个后代的最高节点 .
我发现了几种后缀树的实现 . 以下代码取自here:
use strict;
use warnings;
use Data::Dumper;
sub classify {
my ($f, $h) = (shift, {});
for (@_) { push @{$h->{$f->($_)}}, $_ }
return $h;
}
sub suffixes {
my $str = shift;
map { substr $str, $_ } 0 .. length($str) - 1;
}
sub suffix_tree {
return +{} if @_ == 0;
return +{ $_[0] => +{} } if @_ == 1;
my $h = {};
my $classif = classify sub { substr shift, 0, 1 }, @_;
for my $key (sort keys %$classif) {
my $subtree = suffix_tree(
grep "$_", map { substr $_, 1 } @{$classif->{$key}}
);
my @subkeys = keys %$subtree;
if (@subkeys == 1) {
my $subkey = shift @subkeys;
$h->{"$key$subkey"} = $subtree->{$subkey};
} else { $h->{$key} = $subtree }
}
return $h;
}
print +Dumper suffix_tree suffixes 'bannana$';
对于字符串 "bannana"
,它返回以下树:
$VAR1 = {
'$' => {},
'n' => {
'a' => {
'na$' => {},
'$' => {}
},
'nana$' => {}
},
'a' => {
'$' => {},
'n' => {
'a$' => {},
'nana$' => {}
}
},
'bannana$' => {}
};
另一个实现是从here在线,对于字符串 "bannana"
,它返回以下树:
7: a
5: ana
2: annana
1: bannana
6: na
4: nana
3: nnana
|(1:bannana)|leaf
tree:|
| |(4:nana)|leaf
|(2:an)|
| |(7:a)|leaf
|
| |(4:nana)|leaf
|(3:n)|
| |(5:ana)|leaf
3 branching nodes
问题:
-
如何从这些图表中获取
"an"
和"na"
字符串? -
正如你可以看到树木是不同的,它们是否相同,如果是,为什么它们是不同的,如果不是哪种算法是正确的?
-
如果perl实现错误,是否有perl / python的工作实现?
-
我've read about Ukkonen'的算法也在页面上提到第二个例子(如果在线版本是否使用这个算法我没有抓到),是否使用这个算法提到的任何一个例子?如果不是,使用算法比Ukkonen慢或有任何缺点?
1 回答
1.我如何从这些图表中获取"an"和"na"字符串?
string-node
是从根到此节点的每个节点的连接字符串 .highest node
是最大长度为string-node
的节点 .在第二个问题的答案中见树 .
(3:n)
有2个后代,节点的路径是(2:a)->(3:n)
,连接是an
. 并且(5:a)
得到na
.2.你可以看到树是不同的,它们是否相同,如果是,为什么它们是不同的,如果不是哪种算法是正确的?
这些树是不同的 . 为字符串
"bannana$"
重建第二个树(如在第一个树中):3.如果perl实现错误,是否有perl / python的工作实现?
我不知道Perl,但树是正确构建的 .
4.我在第二个例子的页面上提到的算法(如果在线版本是否使用此算法,我没有抓到),是否使用此算法提到的任何一个例子?如果不是,使用算法比Ukkonen慢或有任何缺点?
我早些时候说过,我在第一个algorthim中的第一行意味着它至少工作
O(n^2)
(n
它是长度字符串):Ukkonen的算法工作线性时间
O(n)
.第一种算法也是递归的,可能会影响已用内存 .