如何从后缀树中得到子串中最长的重复字符串
我需要找到子串中最长的重复字符串。 假设我有字符串"bannana"
维基百科说：
在计算机科学中，最长的重复子串问题是找到至少出现两次的字符串中最长的子串的问题。 在带有字符串“ATCGATCGA $”的图中，最长的重复子串是“ATCGA”
所以我假设字符串"bannana"有两个同样长的子字符串（如果不正确的话）： "an"和"na" 。
维基百科还说，为此目的使用后缀树。 在这里更具体的是引用如何做到这一点（这在我看来比维基百科定义更可靠）：
构建一个后缀树，然后找到具有至少2个后代的最高节点。
我发现了几个后缀树的实现。 以下代码取自：
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$' => {}
};
另一个实现是从这里在线，对于字符串"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"字符串？ 1.我怎样才能从这些图表中得到“an”和“na”字符串？
构建一个后缀树，然后找到具有至少2个后代的最高节点。
string-node为从根节点到此节点的每个节点连接字符串。 highest node是具有最大长度string-node 。
第二个问题在我的答案中见树。 (3:n)有2个后代，节点的路径是(2:a)->(3:n) ，连接是an 。 也为(5:a)得到na 。
2.正如你可以看到树木不同，它们是否等价，如果是，为什么它们不同，如果不是，哪种算法是正确的？
这些树是不同的。 为字符串"bannana$"重建第二棵树（如第一棵树）：
8: $
7: a$
5: ana$
2: annana$
1: bannana$
6: na$
4: nana$
3: nnana$
|(1:bannana$)|leaf
tree:|
| | |(4:nana$)|leaf
| |(3:n)|
| | |(7:a$)|leaf
|(2:a)|
| |(8:$)|leaf
|
| |(4:nana$)|leaf
|(3:n)|
| | |(6:na$)|leaf
| |(5:a)|
| | |(8:$)|leaf
|
|(8:$)|leaf
5 branching nodes
3.如果perl实现是错误的，perl / python是否有任何工作实现？
我不知道Perl，但树已正确构建。
4.我读过关于Ukkonen的算法，这个算法在第二个例子中也提到过（如果在线版本使用这个算法，我没有理解），使用这个算法的任何提到的例子？ 如果没有，与Ukkonen相比，算法是否使用较慢或有什么缺点？
我前面说的，我不知道Perl的，但它在第一algorthim线意味着它可以至少O(n^2) n它是长度的字符串）：
map { substr $str, $_ } 0 .. length($str) - 1;
Ukkonen算法的工作原理是线性时间O(n) 。
第一种算法也是递归的，这可能会影响已用内存。
链接地址: http://www.djcxy.com/p/40111.html上一篇: how to get longest repeating string in substring from suffix tree