问题标签 [suffix-array]

经过相当多的阅读，我已经弄清楚了后缀数组和 LCP 数组代表什么。

后缀数组：表示数组每个后缀的 _lexicographic 等级。

LCP 数组：包含两个连续后缀之间的最大长度前缀匹配，在它们按字典顺序排序后。

几天以来，我一直在努力理解后缀数组和 LCP 算法究竟是如何工作的。

这是取自Codeforces的代码：

我不能，只是不能理解这个算法是如何工作的。我试着用铅笔和纸做一个例子，并写了所涉及的步骤，但至少对我来说太复杂了，但在两者之间失去了联系。

任何关于解释的帮助，使用一个例子，都非常感谢。

您会得到一个不带任何空格的字符串示例“Iamastudent”。您将获得一个预定义的字典功能，该功能可验证给定单词是否存在于字典中。使用此功能，您必须在字符串中插入空格并将其打印为“我是学生”。

这是我的面试问题，并告诉我也用 C++ 解决，我使用动态编程解决了它，但他不满意我给出的解决方案与下面的问题相同

给定一个没有空格的短语，添加空格以构成正确的句子

他让我使用trie或后缀数组来做，但我想不出任何人都可以帮助我的解决方案

cocos2d 为资源添加后缀的方式类似于 "@2x" 适用于通常的 iOS 应用程序。我还想将这些图片放入精灵表中。

问题是一个默认的 cocos2d spritesheet 表示为一个 png 和一个带有 sprite 帧的 plist 文件。

那么如何强制cocos2d引擎在需要的时候将这些后缀应用到plist文件中呢？

如何修改Ukkonen 论文中的过程以保存一个单词在文本中出现的次数的值。是否有任何这样的实现也可以提供字符串频率？

我想要的修改就像一个字符串“hehe”，所有“h”、“e”、“he”的频率计数在树中应该是 2。其余节点的默认值为 1。

我发现了一些迄今为止最好的库和一些以前的问题。

但是他们都没有描述我的问题的足够好的解决方案。我还必须处理一个非常大的字典文件（大约十亿字）。然后算法需要非常快。我准备在空间上妥协一点。

我们可以使用后缀树来计算不同子序列（而不是子字符串）的数量吗？

定义：字符串的子序列是一个新的字符串，它是从原始字符串中删除一些字符而不干扰其余字符的相对位置而形成的。（即，“ACE”是“ABCDE”的子序列，而“AEC”不是）。

那么如果给定一个字符串 S = "rabbbit"，子序列 P = "rabbit" 的模式，我们可以使用后缀树找出 S 中 P 的不同子序列的数量吗？

它应该从人工检查中返回 3。

如果有人愿意通过绘制“兔子”的后缀树来解决这个问题，我将非常感激。

注意 - 我们可以使用 DP 等其他技术来解决这个问题，但我更感兴趣的是我们是否可以使用后缀树来解决它。谢谢！

我已经尝试过在论文http://webglimpse.net/pubs/suffix.pdf中的理论

但是当他们说我有点迷茫

令 Ai 为第一个桶中的第一个后缀（即 Pos[0] = i），并考虑 Ai-h（如果 ih < 0，那么我们忽略 Ai 并取 Pos[1] 的后缀，依此类推） . 由于 Ai 从最小的 h 符号字符串开始，Ai-h 应该是其 2h 桶中的第一个。

我无法理解这种说法。为什么如果 ih < 0 可以忽略 Ai-h。当阶段 1 中 ih > 0 时，如何在 const time 中确定位置？

一个示例 impl 是http://belbesy.wordpress.com/2012/10/10/spoj-649-distinct-substrings-suffix-arrays-nlgn/

我正在讨论 DC3 算法，即用于构建后缀数组的线性时间算法。我无法理解本文中可以找到的技术here。

我无法理解论文第 6 页提到的重命名是如何完成的。如何按照步骤 1 进行重命名。附录中的相关代码部分是：

请帮助我理解这部分。（此代码来自pdf的第20页）

我试图通过 qsort() 对字符串的后缀进行排序，但没有得到排序列表。

我该怎么办 ？
这是我所做的：

这是我的 compare() 函数：

问题是我得到了未排序的列表。

我正在阅读有关 DC3 以构造后缀数组的论文。我想知道为什么DC3不能作为DC2应用，这样计算会更快？

我一直在尝试确定后缀树或后缀数组（包括它们的变体）是否更节省空间（在下面给出的其他属性中），但我似乎根据我的看法提出了不同的观点。例如，这篇wikipedia article建议后缀数组更节省空间。在本书中，在第 1.6 节中，基于 Kunihiko Sadakane 的论文“具有完整功能的压缩后缀树”，建议（压缩）后缀树对空间非常有效。那么关于后缀树和后缀数组（包括它们的变体）之间比较的最新研究是什么？更具体地说，我有兴趣知道在 i) 构造、ii) 空间（理论和实践）、iii) 查询性能方面哪个更好。

我知道这个问题的一部分之前可能已经被问过，但这些问题至少有一年的历史了，我对最新的研究很感兴趣。