问题标签 [suffix-array]

我在 Ruby 中找到了后缀数组的实现并对其进行了一些更改。这是我所拥有的：

它工作得很好，但它没有找到我想要的所有子字符串。例如

如何更改算法以使其找到我想要的所有子字符串？

来自编程珍珠的第 15.2 节

C代码可以在这里查看：http ://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

当我使用后缀数组在 Python 中实现它时：

我发现这idx.sort一步很慢。我认为这很慢，因为 Python 需要按值而不是按指针传递子字符串（如上面的 C 代码）。

测试文件可以从这里下载

C 代码只需 0.3 秒即可完成。

但是对于 Python 代码，它永远不会在我的计算机上结束（我等了 10 分钟并杀死了它）

有谁知道如何使代码高效？（例如，少于 10 秒）

我正在阅读Suffix Arrays，构建一个的代码很简单。但是我找到的所有资源通常都使用一个简单的示例文本banana来解释这个概念。
因此，尽管示例文本很简单，并且后缀数组显示为 ( a, ana, anana, banana, na, nana)，但据我所知，这可以应用于任何类型的文本。
但我不明白，因为文本有空格、换行符、标点符号等。
那么这如何适用于任何类型的文本？

我无法理解以下内容：
我们有 String ABRACADABRA。我们以分组为例： S分组：

S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...> where<>表示一个数组，S[i] 表示Sposition 中的字符i。

我期待这一点，S0=<S[0]S[4]S[8]S[11]>但根据我阅读的书中的“解决方案”，它S0=[ABR][ACA][DAB][RA]本质上不是S[0]S[3]S[6]S[9].
那么我在公式中读错了S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...>什么？

如果重要的话，它来自我读过的关于后缀数组的一章。我只有公式有问题

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

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

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

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

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

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

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

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

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

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

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

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

如果我想找到 2 个字符串的最长公共子字符串，那么哪种方法在时间/空间复杂度方面更有效：使用 DP 的后缀数组？

DP 将产生 O(m*n) 空间，时间复杂度为 O(m*n)，后缀数组方法的时间复杂度是多少？

1) 计算后缀 O(m) + O(n) 2) 排序 O(m+n log2(m+n)) 3) 找到 m+n-1 个字符串的最长公共前缀？[我不确定如何计算 #of 比较]

后缀数组允许我们对子字符串做更多的事情（比如搜索子字符串等），但是由于在这种情况下不需要其他函数，DP 是否会被认为是一种更简单/更清洁的方法？哪一个应该在我们比较 2 个字符串的情况下使用？

另外，如果我们有超过 2 个字符串怎么办？

输入：两个字符串 A 和 B。

输出：一组重复的、不重叠的子串

我必须找到所有重复的字符串，每个字符串都必须在两个（！）字符串中至少出现一次。例如，让

A = "xyabcxeeeyabczeee" 和 B = "yxabcxabee"。

那么一个有效的输出将是 {"abcx","ab","ee"} 但不是 "eee"，因为它只出现在字符串 A 中。

我认为这个问题与“超最大重复”问题非常相关。这是一个定义：

最大重复对：S 中的一对相同的子串 alpha 和 beta，这样在任一方向上扩展 alpha 和 beta 都会破坏两个字符串的相等性它表示为三元组（位置 1，位置 2，长度）

最大重复：“出现在 S 中的最大对中的 S 的子串”。示例：S 中的 abc = xabcyiiizabcqabcyrxar。注意：可以有许多最大重复对，但只能有有限数量的最大重复。

超最大重复“永远不会作为任何其他最大重复的子串出现的最大重复”示例：S 中的 abcy = xabcyiiizabcqabcyrxar。

查找所有超最大重复的算法在“字符串、树和序列的算法”中进行了描述，但仅适用于后缀树。

它的工作原理是：1.) 使用 DFS 查找所有左分集节点

对于 S 中的每个位置 i，S(i-1) 称为左字符 i。T(S)中叶子的左字符是该叶子表示的后缀位置的左字符。如果在 v 的子树中至少有两个叶子具有不同的左字符，则 T(S) 中的内部节点 v 称为左分集。

2.) 在这些节点上应用定理 7.12.4：

当且仅当 v 的所有子节点都是叶子并且每个子节点都具有不同的左字符时，左多样化内部节点 v 表示超最大重复 a

字符串 A 和 B 可能都必须连接起来，当我们在第二步中检查 v 的叶子时，我们还必须施加一个额外的约束，即字符串 A 和 B 中必须至少有一个不同的左字符。这可以通过将它们的位置与 A 的长度进行比较。如果位置（左字符）> 长度（A），则左字符在 A 中，否则在 B 中。

你能帮我用后缀 + lcp 数组解决这个问题吗？

我需要一个后缀树 Java 实现。经过一番谷歌搜索后，我得出结论，libdivsufsort C 实现是最好的。是否有相同（或几乎一样好）质量的 Java 实现，并且最好是开源的。实现应该是生产代码，而不是概念验证代码。

刚刚查看了关于后缀数组的http://en.wikipedia.org/wiki/Suffix_array 。
它说它需要 O(n long) 空间，而字母的大小是 sigma。空间需求将是 O(blog sigma) 位？

想不出两个人的想法。。

这是我对后缀数组的了解。
后缀数组是具有 n 个整数的整数数组。那么，它需要 O(n)*8 个字节吗？作为一个整数，我们需要 8 个字节。而对于数组本身，我们需要 O(n) 个字节吗？假设有 n 个字符。

这是 Suffix Array的一个实现。在最坏的情况下，我在维基百科文章结构中的问题是 o(n)

所以在我的建设中：

1. 我正在使用 stl sort 对字符串的所有后缀进行排序。在最坏的情况下，这可能至少是 O(nlogn)。所以我在这里违反了 O(n) 构造。
2. 第二个是在构造一个最长的公共前缀数组构造时给出 O(n)。但我认为我在 O(n^2) 中的实现

所以对于第一个，即排序

• 如果我使用计数排序，我可能会减少到 O(n)。如果我使用计数排序，它是否正确？我的理解是否正确？让我知道我的理解是否错误

• 有没有办法在 O(n) 时间内找到 LCP？