问题标签 [suffix-array]

我有一个后缀数组。如何获取一个字符串，哪个后缀数组将等于给定数组？

例如。让我有这个数组：[7, 6, 4, 2, 1, 5, 3]。然后字符串banana$对我有好处，因为get_suffix_array(banana$) == [7, 6, 4, 2, 1, 5, 3].

我在互联网上搜索：我发现了许多使用后缀树但不使用后缀数组的 k 重复子串的解决方案。

给定字符串：abaabbabb

最大重复子字符串数，k = 字符串长度 = 6

最初 a[0..k]={0}

子字符串的频率：“a”= 4 因此 a[4]=1；

子字符串的频率：“ab”= 3 因此 a[3]=1；

子串的频率：“b”= 4 因此 a[4]= a[4]+1 = 2；等等..

复杂性：< O(nlogn) 用于数组生成。

使用后缀数组：

“abaabbabb”的后缀：

但是使用 C++ 很容易实现，因为算法头文件中有内置Sort()函数。
我已经经历了形成数组的朴素方法和 O(nlogn) 方法。在这两种情况下，该sort()函数都用于对后缀进行排序。

C中有什么好的方法吗？

我想为字符串的所有子字符串构建一个节省空间的后缀树；假设字符串的长度为 5000，则子字符串的数量约为 25*10^6，并且对于每个节点，我都存储一个大小为 26 的链接数组，因此总内存 = 26*5000*5000，这是不可能的，因此运行时错误是期待。我有一个节省空间的后缀特里树的解决方案，我们在其中压缩我们没有选择的路径，因此空间的顺序大致变为线性。但我无法理解，所以任何人都可以帮助我解决这个问题。

你得到一个字符串，根据那里的频率找到所有排序（降序）的子字符串的频率。

例如：ababa {“a”、“b”、“a”、“b”、“a”、“ab”、“ba”、“ab”、“ba”、“aba”、“bab”、“aba "、"abab"、"baba"、"ababa"}。

输出：

3,2,2,2,2,1,1,1,1

解释

3 a 2 b 2 ba 2 aba 2 ab 1 abab 1 baba 1 ababa 1 bab

解决方案

1）一个明显的解决方案是将所有字符串保留在哈希图中并计算它的频率，但它需要 o(n^3logn) O(n^2 *n){n^2 个子字符串 *O(n) 进行比较字符串*logn（因为地图维护为红黑树）} 2）在三叉搜索树中插入所有子字符串，然后检索每个子字符串的频率，然后对频率进行排序O（n ^ 3 logn）

我想知道是否存在 O(n^2) 或 O(nlogn) 解决方案。

像这样http://www.quora.com/Given-a-string-how-do-I-find-the-number-of-distinct-substrings-of-the-string

给定一个字符串S，我想计算出现n次的子字符串的数量（1 <= n <= s.length()）。我已经用滚动哈希完成了完成了，它可以通过使用后缀树来完成。如何使用复杂度 O( n^2 ) 的后缀数组来解决它？

就像 s = "ababaab"

n 字符串数

4 1 "a" (子串 "a" 出现 4 次)

3 2 "b" , "ab" （子字符串 "b" 和 "ab" 出现 3 次）

2 2 "巴" , "巴"

1 14 "aa" , "bab" , "baa" , "aab" , "abab" ....

我正在学习 Suffix 数组，并从本教程中成功学习了如何在 O(nlognlogn) 时间内制作 Suffix 数组。

现在我想知道如何在 O(nlogn) 时间内从我的后缀数组创建 LCP 数组，或者显然我知道 O(n*n) 方法。我想要更好的东西

我找不到任何好的在线资源请帮助我，这样我就可以完全学习这个主题，它会帮助其他人。

谢谢

假设我们有字符串香蕉的后缀列表-香蕉，anana，nana，ana，na，a。我能够将每个后缀放在一个桶中。像以“a”开头的后缀将在一个桶中，以“b”开头的后缀将在另一个桶中。n 也一样。但是我无法有效地按字典顺序对存储桶中的字符串进行排序。说桶 a 应该是这样的 - a, ana, anana。因此，我无法在 java 中有效地解决这个问题 - http://www.spoj.com/problems/SARRAY/ 我已经被困了好几天了。非常感谢任何一段代码/建议。

我最近一直在更新我的算法知识，并一直在阅读后缀数组。我读过的每个文本都将它们定义为单个搜索字符串上的后缀数组，但有些文章提到它“微不足道”以概括为整个搜索字符串列表，但我不知道如何。

假设我正在尝试对单词列表进行简单的子字符串搜索，并希望返回与给定子字符串匹配的单词列表。天真的方法似乎是在我的列表中的单词之间插入词典结束字符“$”，将它们连接在一起，并从结果中生成一个后缀树。但这似乎会产生大量不相关的条目。如果我创建一个“banana$muffin”的源字符串，那么我最终会为“ana$muffin”生成我永远不会使用的后缀。

我将不胜感激有关如何正确执行此操作的任何提示，或者更好的是，指向一些处理这种情况的算法文本的指针。

我是算法复杂性的新手，因此无法弄清楚以下两种算法的复杂性。两者都找出给定字符串的后缀数组。第一个是我自己创建的，第二个是我在网上找到的。我想知道其中哪个更快，为什么？

第一种算法

第二种算法