3

我不想直接解决这个问题的根源，但这是一个链接：

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

S1 = "banana"
S2 = "panama"

SuffixArray.add S1, S2

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

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

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

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

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

m = anananan
n = anananana

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

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

这是当时的问题，也是我最终将问题减少到的地方。给定一个按我上面描述的方式按字典顺序排序的后缀列表（由多个字符串组成）：

计算最长公共前缀数组的有效方法是什么？.

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

脚注，我不想看到已实现的算法，我不介意被告知去阅读有关该主题的某本书或资源，因为无论如何我在尝试这些挑战时都会这样做。

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

4

1 回答 1

2

阅读

我会推荐斯坦福的本教程 pdf。

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

提示

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

从教程：

让我们用 A(i,k) 表示从位置 i 开始的长度为 2^k 的 A 的子序列。A(i,k) 在 A(j,k) 子序列 (j=1,n) 的排序数组中的位置保留在 P(k,i) 中。

和

使用矩阵 P，可以从最大的 k 向下迭代到 0，并检查 A(i,k) = A(j,k)。如果两个前缀相等，则找到长度为 2^k 的公共前缀。我们只需要更新 i 和 j，将它们都增加 2^k 并再次检查是否有更多常见的前缀。

于 2013-01-11T20:02:15.170 回答