algorithm - 后缀数组标记内部节点

Question

了解内部节点对后缀树很有帮助，因为它们可以帮助您解决诸如查找最长重复子串之类的问题。

这些很难在现场构建（想想白板面试）。所以人们告诉我要研究后缀数组。

我有一个两部分的问题：

1.可以不先建后缀树就创建后缀数组吗？据我所知，大多数实现都构建了 trie，然后遍历它来创建一个后缀数组。

2.给定一个后缀数组，如何识别内部节点？

Answer 1

（在我看来，这对于白板面试来说是一个非常困难的问题......）

要回答第 1 部分，是的，可以（并且通常）直接构造后缀数组。

这个到 stanford.edu 的链接给出了一个很容易实现的简短 O(nlog^2n) 算法：

#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
#define MAXN 65536
#define MAXLG 17
char A[MAXN];
struct entry { int nr[2], p;
} L[MAXN];
int P[MAXLG][MAXN], N, i, stp, cnt;
int cmp(struct entry a, struct entry b)
{
  return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
}
int main(void)
{
  gets(A); for (N = strlen(A), i = 0; i < N; i ++)
  P[0][i] = A[i] - 'a';
  for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1) {
    for (i = 0; i < N; i ++)
      { L[i].nr[0] = P[stp - 1][i];
        L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
        L[i].p = i; }
    sort(L, L + N, cmp);
    for (i = 0; i < N; i ++) P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ?
    P[stp][L[i - 1].p] : i;
  } return 0;
} 

该 PDF 还讨论了如何在实际示例中使用后缀数组。

或者，这篇2005 年的论文“Linear Work Suffix Array Construction”给出了一种用 50 行代码构建后缀数组的 O(n) 方法。

在我对长度为 100k 的字符串的实验中，我发现后缀树（使用 Ukkonen 的 O(n) 算法）需要 16 秒，O(nlog^2n) 后缀数组需要 2.4 秒，而 O(n) 后缀数组需要 0.5 秒。