查找没有后缀数组或后缀树的最长重复子串

Question

最长的重复子串问题如下：

给定一个字符串w，找到至少出现在两个位置的w的最长子串。

这个问题可以在线性时间使用后缀树解决，在线性时间使用增强的后缀数组解决。

我的问题是——对于这个问题，有没有不涉及后缀树或后缀数组的线性时间算法？我很好奇，因为后缀树和后缀数组很难编码和操作，如果有一种算法解决这个问题，而不需要这些其他结构的编码或内存开销，那就太好了。

谢谢

Answer 1

在对此进行了一段时间的挖掘后，我确实找到了后缀树和后缀数组的替代方案。实现本身很简单，就像您想要的那样，但即使代码（大致）在简洁性上很高，但在直觉上却极低。

格拉斯哥大学的Robert W.Irving和Lorna Love撰写了一篇论文《后缀二叉搜索树和后缀AVL树》，提出了后缀树和后缀数组的替代解决方案。作者声称，与后缀树相比，管理和构建后缀二叉搜索树要简单得多，并表明，在后缀AVL树的情况下，构造时间可以保证不超过O（n log（n））（在平均情况下，对于标准的非平衡原始BST也是如此，但在最坏的情况下，它可以降级为O（n^2））。

当然，这比传统的后缀树更糟糕，因为在SBST中找到最长重复子串的时间是以构建它的时间为界的。所以，严格来说，这并没有回答你的问题，但我决定发布这个以供将来参考和感兴趣的读者。

此外，本文还指出，生成的树是传统后缀树和后缀数组的有力替代品。这篇论文是围绕着在建立树之后在对数时间内找到一个模式的问题而写的。你可以从Citeserx下载。

其思想是，每个节点都与一个整数i关联，其中i是该节点表示的后缀在目标文本中的第一个字符的偏移量。对于长度n的给定字符串[a1，a2，a3，…，an]，将有n节点，节点i表示后缀[ai，ai 1，…，an]。

本文没有解决确定最长重复子串的问题，但提出的建立二叉搜索树的方法使得解决最长重复子串问题变得容易。一旦我讲到建造过程，我会进行扩展。为了理解解决最长重复字符串问题的扩展，理解如何构建树是至关重要的（否则代码看起来会很神奇）。

因此，我将首先解释这棵树是如何建造的，并将根据我从论文中得到的想法来建造。本文讨论了形式证明以及其他细节（包括如何将其转化为AVL树）。你可以自由地跳到前面的部分，在那里我讨论了如何扩展算法，但请记住，如果你这样做，可能很难理解。

本文描述了一种在后缀二叉查找树中搜索模式的优化算法，该算法避免在我们访问的每个节点上从头开始将模式与来自节点的后缀进行比较。在最坏的情况下，这样做需要l*m字符比较，其中m是模式的大小，l是搜索路径。我们不想在每个节点上从头开始比较字符来决定分支的方向；相反，最好最多比较一次模式中的每个字符。如果我们为每个节点存储两个附加属性，这是可能的。构建树的过程与这种优化（以及我提出的扩展）紧密相关，因此理解它非常重要。

首先，一些术语：对于给定的节点i，如果i位于j的左子树中，则称节点j为i的右祖先。左祖先的定义类似。i最近的右祖先是节点j，因此j的后代不是i的右祖先；同样，一个类似的定义也适用于最近的左祖先。从现在起，我将使用缩写形式cra（I）来指代I最接近的右祖先，I最接近的左祖先缩写为cla（I）。我们还定义了两个节点j和i之间最长的公共前缀，并将其表示为lcp（i，j）。

对于给定的节点i，我们将存储两个属性，m（i）和d（i）m（i）表示lcp（i，j）最高的值，其中j是i的祖先集。注意，由于二叉树的属性，节点j要么是cla（i）要么是cra（i）d（i）是跟踪m（i）来源的属性；如果j==cla（i），则d（i）是RIGHT（意味着i位于lcp（i，j）最大化的节点j的右子树中），否则，d（i）是LEFT。

下面是一组定理，它们共同构建了在SBST中搜索给定模式的基本算法。这些定理描述了当模式搜索到达节点i时该做什么。请参考论文中的正式证明，我将尝试提供一个直观的证据，说明为什么规则是这样的。这些定理共同构成了一组规则，允许算法通过最多一次比较模式中的每个字符来搜索模式，这非常简洁！

当搜索到达节点i时，我们使用两个值，llcp和rlcpllcp是lcp（pattern，j）最高的值，其中j是i的所有正确祖先的集合rlcp是相同的，但最大值将接管i的所有左祖先。同样，由于二叉树的属性，llcp只是lcp（pattern，cra（i）），而rlcp是lcp（pattern，cla（i））。

在深入研究定理之前，我认为在一张纸上绘制一个样本SBST并在树上可视化每个定理的语义含义是一个好主意。

定理1是最简单的，涵盖了m（i）的情况

定理2处理mi的情况

案例1:max（llcp，rlcp）=llcp

如果max（llcp， rlcp）==llcp，则表示该模式与节点i最接近的右祖先的共同点比与其最接近的左祖先的共同点更多。此外，因为llcp

关于llcp和rlcp的更新呢？因为我们的分支是正确的，cra（i）在下一次迭代中将是相同的，所以llcp保持不变。更新rlcp有点棘手。当我们向右分支时，新的cla将是节点i。接下来发生的事情取决于m（i）是来自cra（i）还是cla（i）。我们可以使用d（i）来知道：如果m（i）来自cra（i），那么d（i）=左，否则，d（i）=右。

案例1.1：max（llcp， rlcp）==llcp

在这种情况下，我们知道m（i）来自cla（i），这意味着节点i与cla（i）比cra（i）有更多的共同点（记住，该模式与cra（i））。正如我们之前看到的，我们将向右分支，这使得模式大于i。这意味着cla

案例1.2:max（llcp，rlcp）=llcp

现在，我们知道m（i）来自cra（i），但该模式与cra（i）的共同点比i与cra（i）。这意味着节点i充当“瓶颈”，使rlcp变小-rlcp只能与i和cra（i）之间的公共前缀一样大，等于m（i）。所以，在这种情况下，rlcp与m（i）相同。

对于反向情况可以执行类似的分析，其中max（llcp， rlcp）==rlcp（然后考虑子情况d（i）==右和d（i）==LEFT）。要执行的操作是前面案例的反向版本：我们向左分支，rlcp保持不变，llcp变成m（i）如果d（i）==右，否则，它保持不变。

简而言之：

定理2结果

                                   d(i) == RIGHT                d(i) == LEFT                      

max(llcp, rlcp) == llcp |            branch right        |   branch right; rlcp = m(i)
max(llcp, rlcp) == rlcp |       branch left; llcp = m(i) |         branch left

定理3探讨了当m（i）等于另一个祖先模式的最长公共前缀时的两种情况。特别是，如果m（i）=llcp

定理4是我们必须执行实际字符比较的地方。每次我们无法推断模式和当前节点之间的相对顺序时都会发生这种情况，即当m（i）==rlcp==llcp，或m（i）==llcp

定理3

                                     d(i) == RIGHT                d(i) == LEFT                      
m(i) == llcp && llcp > rlcp |         branch right       |               *
m(i) == rlcp && rlcp > llcp |             *              |         branch left

* = compare(); if branch == left then rlcp = computed_lcp else llcp = computed_lcp

这是将所有这些结合在一起的伪代码，取自第9页：

我对算法的修改

你可能需要花一点时间来理解这个算法的惊人之处，但是一旦你掌握了所有的细节，就可以看出，找到最长重复子串的问题相当于找到m（i）最大的节点。毕竟，最长的重复子串是任何两个节点之间可以找到的最长的公共前缀。如果我们在构建树时跟踪它，则可以在没有任何显着开销的情况下找到它：必须保留迄今为止看到的最大m（i），并且每当插入新节点j时，我们将m（j）与迄今为止看到的最大值进行比较，如果m（j）更大，则更新它。事实上，这种方法只不过是一种实现算法的奇特方式，该算法等效于对所有后缀进行排序并在任何两个连续后缀之间找到最长的公共前缀，其优点是不执行不必要的字符比较。这是一个相当好的改进。

上面显示的伪代码几乎足以构建标准SBST。我们从添加一个根节点开始，用i==1表示整个文本。然后从左到右添加后缀。要插入一个新的后缀i，我们搜索后缀为i的模式。这样做会使算法在插入的确切位置停止。但是，本文没有详细介绍插入过程。我们必须小心定理4的最终料中的返回i；。我们只能在搜索时返回。如果我们正在进行插入并到达一个节点，使我们达到定理4的情况，那么这意味着新后缀中的所有字符都与之前插入的后缀匹配。因为后缀是从左到右插入的，我们也知道新后缀的字符比另一个少，这意味着新后缀比另一个低：正确的移动是向左分支。由于我们向左分支，最近的左祖先保持不变，因此我们只需要更新llcp。llcp成为后缀本身的大小，因为正如我们所看到的，所有这些都与现在最接近的右祖先的节点匹配。

显然，新节点的m（i）值将等于max（llcp，rlcp），并且d（i）根据定义，如果max（llcp，rlcp）==rlcp，则d（i）将是RIGHT，否则是LEFT。

我在C中的实现归结为伪代码和插入逻辑。有两种数据结构：struct sbst表示后缀二叉搜索树，以及迄今为止看到的最大m（i）；和struct node，它是树节点的描述符。

以下是完整的程序列表：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEFT 0
#define RIGHT 1
#define MODE_INSERT 1
#define MODE_FIND 2
#define MAX_TEXT_SIZE 1024
#define max(a,b) ((a)>(b)?(a):(b))

struct node {
  int m;
  int d;
  int i;
  struct node *left;
  struct node *right;
};

struct sbst {
  struct node *root;
  int max_mi; /* The maximum lcp in the tree */
  int max_i; /* The node i with m(i) == max_mi */
};

struct node *allocate_node(int m, int d, int i) {
  struct node *new_node = malloc(sizeof(*new_node));
  new_node->m = m;
  new_node->d = d;
  new_node->i = i;
  new_node->left = new_node->right = NULL;
  return new_node;
}

int lcp(char *str1, char *str2);

/* The core where all the work takes place.
   It is assumed that when this function is called, tree->root always points to a valid, allocated root. That is, it is assumed
   that the tree contains at least one node.
   This function provides both a find and an insert algorithm. To find a pattern, <mode> must be MODE_FIND. To insert,
   <mode> must be MODE_INSERT. In the latter case, the parameter <text_i> corresponds to the index in the original string
   of the suffix being inserted (index starts counting at 1, as described in the paper). Also, in MODE_INSERT, the pattern is
   the suffix being inserted.
   If in MODE_FIND, this function returns the index (starting at 1) in the text where <pattern> can be found, or 0 if no such
   pattern could be found.
*/
int find_insert_aux(struct sbst *tree, char *pattern, size_t pattern_len, char *text, size_t text_len, char mode, int text_i) {
  struct node *current, *prev;
  int llcp, rlcp;
  int next_dir;

  current = tree->root;
  llcp = rlcp = 0;

  while (current != NULL) {
    int max_pattern = max(llcp, rlcp);
    if (current->m > max_pattern) {
      next_dir = current->d;
    } else if (current->m < max_pattern) {
      if (llcp > rlcp) {
    next_dir = RIGHT;
    if (current->d == LEFT) {
      rlcp = current->m;
    }
      } else if (rlcp > llcp) {
    next_dir = LEFT;
    if (current->d == RIGHT) {
      llcp = current->m;
    }
      }
    } else if (current->m == llcp && llcp > rlcp && current->d == RIGHT) {
      next_dir = RIGHT;
    } else if (current->m == rlcp && rlcp > llcp && current->d == LEFT) {
      next_dir = LEFT;
    } else {
      int sub_lcp = lcp(pattern+current->m, text+current->m+current->i-1);
      int t = current->m + sub_lcp;
      if (t == pattern_len) {
    if (mode == MODE_FIND) {
      return current->i;
    } else {
      next_dir = LEFT;
      llcp = t;
    }
      } else if (current->i+t-1 == text_len || pattern[t] > text[t+current->i-1]) {
    next_dir = RIGHT;
    rlcp = t;
      } else {
    next_dir = LEFT;
    llcp = t;
      }
    }
    prev = current;
    current = (next_dir == RIGHT ? current->right : current->left);
  }
  if (mode == MODE_INSERT) {
    struct node *new_node = allocate_node(max(llcp, rlcp), (llcp > rlcp ? LEFT : RIGHT), text_i);
    if (next_dir == LEFT)
      prev->left = new_node;
    else
      prev->right = new_node;
    if (new_node->m > tree->max_mi) {
      tree->max_mi = new_node->m;
      tree->max_i = new_node->i;
    }
  }
  return 0;
}

void sbst_insert(struct sbst *tree, char *text, size_t text_size, int i) {
  (void) find_insert_aux(tree, text+i-1, text_size-i+1, text, text_size, MODE_INSERT, i);
}

int sbst_find(struct sbst *tree, char *text, size_t text_size, char *pattern, size_t pattern_size) {
  return find_insert_aux(tree, pattern, pattern_size, text, text_size, MODE_FIND, 0);
}

/* Builds a Suffix Binary Search Tree that keeps track of the highest m(i) as it is built. */
struct sbst *build_sbst(char *text, size_t text_size) {
  if (*text == '\0')
    return NULL;

  struct sbst *tree = malloc(sizeof(*tree));
  tree->root = allocate_node(0, 0, 1);
  tree->max_mi = 0;
  tree->max_i = 1;

 for (int i = 1; text[i] != '\0'; i++)
   sbst_insert(tree, text, text_size, i+1);

  return tree;
}

/* Given an SBST for the input, finds the longest repeated substring in O(1)
   Stores the offset in *offset, and the size of the lrs in *size
*/
void find_lrs(struct sbst *tree, int *offset, int *size) {
  *offset = tree->max_i-1;
  *size = tree->max_mi;
}

/* Debug section */
void dump(struct node *n, char *text, int depth) {
  if (!n)
    return;
  for (int i = 0; i < depth; i++)
    putchar(' '), putchar(' ');
  printf("%d|%d|%d|%s\n", n->m, n->d, n->i, text+n->i-1);
  dump(n->left, text, depth+1);
  dump(n->right, text, depth+1);
}

void dump_sorted(struct node *n, char *text) {
  if (!n)
    return;
  dump_sorted(n->left, text);
  printf("%s\n", text+n->i-1);
  dump_sorted(n->right, text);
}
/* End debug section */

int lcp(char *str1, char *str2) {
  int i;
  for (i = 0; str1[i] != '\0' && str1[i] == str2[i]; i++);
  return i;
}

int main(void) {
  char text[MAX_TEXT_SIZE];
  printf("Enter text, hit RETURN to terminate (max. %d chars): ", MAX_TEXT_SIZE-1);

  fgets(text, sizeof text, stdin);
  size_t text_size = strlen(text);

  /* Trim newline */
  text[--text_size] = '\0';

  struct sbst *tree = build_sbst(text, text_size);

  /* Debug */
  #ifdef DEBUG_MODE
  dump(tree->root, text, 0);
  printf("\n");
  dump_sorted(tree->root, text);
  #endif

  int lrs_offset, lrs_size;
  find_lrs(tree, &lrs_offset, &lrs_size);
  if (lrs_size == 0)
    printf("No longest repeated substring.\n");
  else {
    printf("Longest repeated substring found at offset %d with size %d: %.*s\n", lrs_offset, lrs_size, lrs_size, text+lrs_offset);
  }
  return 0;
}

如果我没有看报纸，我会把这段代码视为黑魔法。

请注意，这并不是最佳软件工程实践的良好演示：不熟悉该算法的人将很难阅读和理解它，它会泄漏内存，不会检查malloc的返回值，并且还有一些其他缺陷，但我认为这足以说明我的观点。

虽然这可能不如后缀树那么理想，但它显然很容易构建，并提供了一个良好的起点。例如，作为副产品，它可以在对数时间内执行模式匹配——这非常好！

注意：我没有太多时间来测试实现。我做了一些基本的测试，它似乎是有效的，但我不能保证没有错误。