string - 寻找想法 : lexicographically sorted suffix array of many different strings compute efficiently an LCP array

Question

我不想直接解决这个问题的根源，但就是这个问题 link :

所以我接收字符串并将它们添加到一个后缀数组中，该数组在内部实现为一个排序集，然后我获得的是两个给定字符串的字典顺序列表。

S1 = "banana"
S2 = "panama"

SuffixArray.add S1, S2

为了高效地搜索 k-th 最小子串，我对这个排序集进行了预处理，以添加有关后缀与其前身之间最长公共(public)前缀的信息，并密切关注累积子串数数。所以我知道对于大于最后一项的累积子字符串计数的给定 k，这是一个无效查询。

这对于问题定义中给出的约束的小输入和随机大输入非常有效，最多 50 个长度为 2000 的字符串。我能够通过 7 个案例中的 4 个，我感到非常惊讶我没有全部拿到。

所以我去寻找瓶颈，它击中了我。给定大量这样的输入

anananananananana.....ananana
bkbkbkbkbkbkbkbkb.....bkbkbkb

第 k 个最小子串的查询仍然像预期的那样快但不是我预处理排序集合的方式...我计算集合元素之间最长公共(public)前缀的方式是不是高效和线性的 O(m)，就像这样，我做了最天真的事情，期望它足够好:

m = anananan
n = anananana

Start at 0 and find the point where `m[i] != n[i]`

之所以这样是因为后缀和他的前身可能没有关系(即来自不同的输入字符串)所以我想我不得不使用暴力。

这是当时的问题，我最终将问题简化为。按照我上面描述的方式(由多个字符串组成)给出一个按字典顺序排序的后缀列表:

计算最长公共(public)前缀数组的有效方法是什么？。

子问题是，我的方法是否完全偏离了目标？如果是这种情况，请提出进一步的调查途径。

脚注，我不想展示已实现的算法，我不介意被告知去阅读某某书籍或有关该主题的资源，因为这就是我在尝试这些挑战时所做的事情.

接受的答案将指导我走上正确的道路，或者在失败的情况下；教我如何从更广泛的意义上解决这些类型的问题的东西，一本书或其他东西

Answer 1

阅读

我会推荐这个 tutorial pdf from Stanford .

本教程介绍了一个简单的 O(nlog^2n) 算法，该算法使用 O(nlogn) 空间来计算后缀数组和中间结果矩阵。中间结果矩阵可用于计算 O(logn) 中两个后缀之间的最长公共(public)前缀。

提示

如果您想尝试自己开发算法，关键是根据字符串的 2^k 长前缀对字符串进行排序。

来自教程:

Let's denote by A(i,k) be the subsequence of A of length 2^k starting at position i. The position of A(i,k) in the sorted array of A(j,k) subsequences (j=1,n) is kept in P(k,i).

和

Using matrix P, one can iterate descending from the biggest k down to 0 and check whether A(i,k) = A(j,k). If the two prefixes are equal, a common prefix of length 2^k had been found. We only have left to update i and j, increasing them both by 2^k and check again if there are any more common prefixes.