问题标签 [suffix-array]

我正在研究在此链接中找到的后缀数组的特定 O(NlogN) 实现：https
://sites.google.com/site/indy256/algo/suffix_array 我能够理解核心概念但理解实现整体来说是个问题。

我想知道 cnt[] 数组的使用以及它有用的地方。任何指针都会有所帮助。

谢谢。

我正在尝试计算 Ruby 中字符串的相似前缀开头的数量。例如; 输入“ababaa”应该输出11；

我已经了解了下面的代码，使用嵌套循环将上述每个作为数组进行遍历，但是看起来 Ruby 当前仅输出第一个 Array 对象“ababaa”的计数。

解决了，谢谢：）

我已经看得很远了，仍然无法解决这个问题，看起来（最终的，嵌套的）数组在“ary”数组的第一次迭代之后中断了，只是返回了那个输出。

I want to find lexicographically Kth smallest substring of a given string when the duplicate substrings are allowed.

Suppose we are given a string abc then its substrings in lexicographical order are {a,ab,abc,b,c}, now suppose we are given K = 3 then ans is abc.

Now suppose we are given string aaa then all its substrings are {a,a,a,aa,aaa,aa} so now if K = 4 then we output aa.

However I came across the following code on codeforces but i am not able to understand it. any help is greatly appreciated.

Here is the link to question http://codeforces.com/problemset/problem/128/B

在 Pre-java 7 中，我可以简单地执行以下操作：

但是，在 Java 7 中， substring 方法返回一个新字符串。所以消耗的空间将是O(n^2)字符串n的长度。

在 Java 7 和更高版本中是否有任何快速简便的方法可以做到这一点？

我收集了大约 5000 万个字符串，每个字符串大约有 100 个字符。我正在寻找非常有效（运行时间和内存使用）的通用后缀树实现。

我已经尝试过https://github.com/npgall/concurrent-trees但即使运行时间很有效，它也会占用大量内存。有 250 万个长度为 100 的字符串。它已经占用了 50GB 的内存。

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

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

我有一个两部分的问题：

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

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

我阅读了 Steven Halim 和 Felix Halim 的书 Competitive Programming 3

我正在阅读关于字符串的章节。我正在尝试理解后缀数组构造算法。我不明白基数排序部分。（虽然，我了解基数排序和计数排序的工作原理）

这是书中的代码

有人可以解释countingSort（）函数的这些行中发生了什么吗？

非常感谢您宝贵的时间。

我正在尝试创建一个返回最长重复子字符串的程序。我几乎找到了解决方案，但由于某种原因，当他忙于查找 LRS 时，我的 strcmp 出错了。有人能解释一下为什么会出现错误以及我如何解决这个问题吗？

编码：

我已经成功地为我正在编写的压缩测试平台实现了 BWT 阶段（使用常规字符串排序） 。我可以应用 BWT，然后应用 BWT 逆变换，输出与输入匹配。现在我想使用后缀数组加快 BW 索引表的创建。我发现了 2 个相对简单的，据说是快速的 O(n) 后缀数组创建算法，DC3和SA-IS，它们都带有 C++/C 源代码。我尝试使用源（开箱即用的编译 SA-IS 源也可以在此处找到），但未能获得正确的后缀数组/BWT 索引表。这是我所做的：

1. T=输入数据，SA=输出后缀数组，n=T的大小，K=字母大小，BWT=BWT索引表

2. 我使用 8 位字节，但两种算法都需要一个零字节形式的唯一哨兵/EOF 标记（DC3 需要 3，SA-IS 需要一个），因此我将所有输入数据转换为 32 位整数，增加所有符号加 1 并附加标记零字节。这是T。

3. 我创建了一个整数输出数组 SA（DC3 的大小为 n，KA-IS 的大小为 n+1）并应用算法。我得到的结果类似于我的排序 BWT 变换，但有些值是奇数（参见更新 1）。两种算法的结果也略有不同。SA-IS算法在前面产生了一个多余的索引值，所以所有的结果都需要向左复制一个索引（SA[i]=SA[i+1]）。

4. 要将后缀数组转换为正确的 BWT 索引，我从后缀数组值中减去 1，进行模运算并且应该具有 BWT 索引（根据此）： BWT[i]=(SA[i]-1)%n .

这是我提供 SA 算法并转换为 BWT 的代码。您应该能够或多或少地插入论文中的 SA 构造代码：

我究竟做错了什么？

更新 1
将算法应用于少量测试文本数据时，例如“yabbadabbado”/“这是一个测试”。/“abaaba”或一个大文本文件（来自坎特伯雷语料库的alice29.txt ）它们工作正常。实际上 toBWT() 函数甚至不是必需的。
将算法应用于包含完整 8 位字节字母表（可执行文件等）的文件中的二进制数据时，它们似乎无法正常工作。将算法的结果与常规 BWT 索引的结果进行比较，我注意到前面有错误的索引（在我的例子中为 4）。索引的数量（顺便说一句？）对应于算法的递归深度。索引指向原始源数据最后出现 0 的位置（在构建 T 时将它们转换为 1 之前）...

更新 2
当我对常规 BWT 数组和后缀数组进行二进制比较时，会有更多不同的值。这可能是意料之中的，因为公平排序不一定与标准排序相同，但由数组转换的结果数据应该相同。它不是。

更新 3
我尝试修改一个简单的输入字符串，直到两个算法都“失败”。更改字符串“这是一个测试”的两个字节后。到 255 或 0（从 746869732069732061 20 74657374 2E h 到例如 746869732069732061 FF 74657374 FF h，最后一个字节必须更改！）索引和转换后的字符串不再正确。将字符串的最后一个字符更改为字符串中已经出现的字符似乎也足够了，例如“这是一个测试”7468697320697320612074657374 73 h。然后转换后的字符串的两个索引和两个字符将交换（比较使用 SA 的常规排序 BWT 和 BWT）。

我发现必须将数据转换为 32 位的整个过程有点尴尬。如果有人有更好的解决方案（论文，更好的是一些源代码）来直接从具有 256 个字符字母的字符串生成后缀数组，我会很高兴。

后缀树或后缀数组可以有效地与数字一起使用吗？

例如：

它可以与数组[1,2,3,4,5,3,9,8,5,3,9,8,6,4,5,3,9,11,9,8,7,11]一起使用以从数组的内容中提取所有可能的不重叠重复的所有大小的子字符串吗？如果是这样，您能否提供相同的实现。我试图达到同样的效果，但还没有找到有效的解决方案。

预期成绩：

考虑数组 : [1,2,3,4,5,9,3,4,5,9,3,3,4,5,9,3]，非重叠重复序列意味着提取的组：3,4,5,9,3源自从索引 2 到 6 和 11 到 15 和 NOT 6 到 10 开始的重复