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

Question

longest repeated substring problem是以下内容:

Given a string w, find the longest substring of w that appears in at least two locations.

可以使用后缀树在线性时间中解决问题，而使用增强后缀数组在线性时间中可以解决此问题。

我的问题是-是否存在不涉及后缀树或后缀数组的线性时间算法？我很好奇，因为众所周知，后缀树和后缀数组很难编码和操作，如果有一种针对该问题的算法而无需其他结构的编码或内存开销，那将是很好的。

谢谢!

Answer 1

在研究了一段时间之后，我确实找到了后缀树和后缀数组的替代方法。实现本身很简单，就像您想要的一样，但是即使代码简洁(大致)很高，但直觉却非常低。

格拉斯哥大学的Robert W. Irving和Lorna Love发表了一篇论文，后缀二进制搜索树和后缀AVL树，提出了后缀树和后缀数组的替代解决方案。作者声称，与后缀树相比，管理和构建后缀二进制搜索树实际上要简单得多，并且表明在后缀AVL树的情况下，可以保证构建时间不超过O(n log(n))(对于标准来说也是如此) ，通常情况下是不平衡的原始BST，但在最坏的情况下，它可能降级为O(n^2)。

当然，这比传统的后缀树还差，因为在SBST中找到最长的重复子字符串的时间受构建它的时间限制。因此，严格来说，这不能回答您的问题，但是我决定将其发布以供将来引用和感兴趣的读者。

此外，该论文指出，生成的树是传统后缀树和后缀数组的有力替代者。本文围绕构建树后在对数时间内找到模式的问题而写。您可以从CiteSeerX下载它。

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

本文没有解决确定最长重复子串的问题，但是提出的构建二分搜索树的方法使解决最长重复子串的问题变得容易。当我谈论构建过程时，我将进行该扩展。了解如何构建树以了解扩展以解决最长的重复字符串问题至关重要(否则代码看起来就像魔术一样)。

因此，我将首先解释树的构建方式，并根据从本文中得到的想法进行解释。本文讨论了形式证明以及其他细节(包括如何将其转变为AVL树)。您可以随意跳到我讨论如何扩展算法的部分，但是请记住，如果这样做，可能很难理解。

本文介绍了一种用于在后缀二进制搜索树中搜索模式的优化算法，该算法避免了在我们访问的每个节点上从头开始从节点将模式与后缀进行比较。在最坏的情况下，这样做将需要l*m字符比较，其中m是模式的大小，而l是搜索路径。我们不想比较每个节点上从头开始的字符来确定分支方向。取而代之的是，希望最多一次比较模式中的每个字符。如果我们在每个节点上存储两个其他属性，则有可能。构建树的过程与该优化(以及我提议的扩展)紧密相关，因此理解它非常重要。

首先，一些术语:对于给定的节点i，如果j在i的左子树中，则将节点i称为j的右祖先。左祖先的定义与此类似。 i的最靠近的右祖先是节点j，因此j的后代都不是i的右祖先；同样，类似的定义适用于最接近的左祖先。从现在开始，我将使用缩写形式i指代cra(i)的最接近右祖先，并将i的最接近左祖先缩写为cla(i)。我们还定义了两个节点j和i之间的最长公共(public)前缀，并将其表示为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时，我们使用2个值llcp和rlcp。 llcp是lcp(pattern, j)最高的值，其中j是i的所有正确祖先的集合。 rlcp相同，但最大值是i的所有左祖先所占。同样，由于具有二叉树的属性，llcp只是lcp(pattern, cra(i))，而rlcp是lcp(pattern, cla(i))。

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

定理1是最简单的，涵盖了m(i) > max(llcp, rlcp)的情况。如果发生这种情况，llcp和rlcp不会改变，因为我们可以像其祖先一样匹配i，并且搜索的分支方向与d(i)相同。要了解原因，请考虑d(i) == LEFT的情况。如果是d(i) == LEFT，则意味着m(i)来自与cra(i)的匹配项。如果我们要访问i，这是因为我们已经知道该模式低于cra(i)和lcp(cra(i), pattern) < lcp(i, cra(i))，这使该模式小于i，所以我们向左移动。可以对d(i) == RIGHT进行相同的处理，因此，实际上，我们只需要遵循d(i)的方向即可。

定理2处理情况mi < max(llcp, rlcp)。这一点很难理解。让我们看看max(llcp, rlcp) == llcp和max(llcp, rlcp) == rlcp会发生什么。

情况1:max(llcp，rlcp)== llcp

如果为max(llcp, rlcp) == llcp，则意味着该模式与节点i的最接近右祖先的共同点要多于与其最接近的左祖先的共同点。此外，由于使用llcp > m(i)，该模式与cra(i)的共同点要多于节点i与cra(i)的共同点。这以及i低于cra(i)(根据BST的定义)的事实，意味着该模式大于i。因此，我们正确分支。

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

情况1.1:max(llcp，rlcp)== llcp && d(i)==正确

在这种情况下，我们知道m(i)来自cla(i)，这意味着节点i与cla(i)的共同点大于与cra(i)的共同点(请记住，该模式与cra(i)的共同点更多)。如前所述，我们将向右分支，这将使模式大于i。这意味着cla < i < pattern以及pattern和i之间的最长公共(public)前缀与pattern和cla之间的相同；换句话说，lcp(i, cla) > lcp(i, pattern)(否则pattern必须小于i)，因此rlcp的lcp(i, pattern)保持不变。

情况1.2:max(llcp，rlcp)== llcp && d(i)==左

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

对于相反的情况，可以执行类似的分析，即max(llcp, rlcp) == rlcp(然后考虑子情况d(i) == RIGHT和d(i) == LEFT)。要执行的操作是先前情况的相反版本:我们向左分支，rlcp保持不变，如果llcp，m(i)变为d(i) == RIGHT，否则，它保持不变。

简而言之:

定理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)等于该模式的另一个祖先的最长公共(public)前缀的两种情况。特别是，如果使用m(i) == llcp && llcp > rlcp && d(i) == RIGHT，我们知道i与cla匹配的方式与cra匹配的方式一样多。由于d(i) == RIGHT和m(i) == llcp，因此遵循lcp(i, cra) < llcp和i < cra，这意味着该模式大于i-我们向右分支。类似的论点适用于相反的情况。如果是m(i) == rlcp && rlcp > llcp && d(i) == LEFT，我们向左分支。在这两种情况下，llcp和rlcp都将保持不变:在前一种情况下，llcp不会改变，因为cra仍然相同，而rlcp不会改变，因为d(i) == RIGHT && m(i) == llcp，即与cla或i匹配模式是相同的;在后一种情况下也是如此。

定理4是我们必须进行实际字符比较的地方。每当我们无法推断出模式与当前节点之间的相对顺序时，即在m(i) == rlcp == llcp或m(i) == llcp && llcp > rlcp && d(i) == LEFT或反向m(i) == rlcp && rlcp > llcp && d(i) == RIGHT时，都会发生这种情况。直觉上，我们知道对顺序没有任何推断，并且字符比较从不属于最长公共(public)前缀的第一个字符开始，然后在不同的第一个字符处停止(此时我们可以推理出命令)。同样，如果我们向右分支，则cra保持不变，因此llcp不变，并且rlcp现在将保留模式和节点i之间新计算的最长公共(public)前缀的值。相反的情况发生类似的过程:我们向左分支，rlcp保持不变，并且llcp成为先前计算出的最长公共(public)前缀的值。这个定理在直觉上是正确的，因此我不再赘述。

定理3和4的结果

                                     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页:

我对算法的修改

可能需要花费一些时间来解决这个算法的问题，但是一旦掌握了所有细节，就可以发现找到最长重复子串的问题等同于找到i最大的节点m(i)。 。毕竟，最长的重复子字符串是在任何两个节点之间可以找到的最长的公共(public)前缀。如果我们在构建树时一直跟踪它，就可以发现这没有任何大的开销:必须保留到目前为止看到的最大m(i)，并且每当插入新节点j时，我们就将m(j)与到目前为止看到的最大值进行比较，并进行更新如果m(j)更大，则为true。实际上，这种方法无非是一种花哨的方式来实现一种算法，该算法等效于对所有后缀进行排序并找到任意两个连续后缀之间的最长公共(public)前缀，其优点是不执行不必要的字符比较。这是一个相当不错的改进。

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

显然，新节点的m(i)值将等于max(llcp, rlcp)，根据定义，如果d(i)，RIGHT将为max(llcp, rlcp) == rlcp，否则为LEFT。

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

这是完整的程序 list :

#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的返回值，并且还有其他一些缺陷，但是我认为这足以说明我的观点。

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

注意:我没有太多时间来测试实现。我进行了一些基本测试，但似乎可以正常工作，但是我不能保证没有错误。