如何从后缀树中获取子串中最长的重复字符串

Question

我需要找到子串中最长的重复字符串.假设我有字符串"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

问题:

1. 如何从这些图形"an"和"na"字符串中获取？
2. 你可以看到树是不同的,它们是否相同,如果是,为什么它们是不同的,如果不是哪种算法是正确的？
3. 如果perl实现错误,是否有任何perl/python的工作实现？
4. 我已经读过关于Ukkonen的算法,这个算法也在第二个例子的页面上提到过(如果在线版本是否使用这个算法我没有抓到),是否有任何提到的例子使用这个算法？如果不是,使用算法比Ukkonen慢或有任何缺点？

Answer 1

1. 如何从这些图中得到“an”和“na”字符串？

构建一棵后缀树，然后找到具有至少 2 个后代的最高节点。

string-node是连接从根到该节点的每个节点的字符串。highest node是具有最大长度的节点string-node。

请参阅我对第二个问题的回答中的树。(3:n)有 2 个后代，到节点的路径是(2:a)->(3:n)，连接是an。也适用于(5:a)get 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，但它是第一个算法中的一行意味着它至少可以工作O(n^2)（n它是长度字符串）：

map { substr $str, $_ } 0 .. length($str) - 1;

Ukkonen 的算法工作时间为线性O(n)。

第一个算法也是递归的，这可能会影响使用的内存。