问题标签 [suffix-array]

后缀数组将索引给定字符串列表的所有后缀，但是如果您尝试索引所有可能的唯一子字符串怎么办？我对此有点陌生，所以这是我的意思的一个例子：

给定字符串

后缀数组索引（至少在我的理解中）

我想索引（所有子字符串）

我正在寻找后缀数组吗？如果是这样，我该怎么做才能索引所有子字符串？如果没有，我应该在哪里寻找？另外我会用谷歌来对比“所有子字符串”与“后缀子字符串”吗？

我有一个由特殊字符（B、C、D、F、X、Z）随机生成的字符串，例如生成以下字符串列表：

我还有一个模式列表，即匹配生成的字符串并返回最佳模式并从字符串中提取一些字符串。

字符串模式

例如，

B D Z Z Z C D C Z, 有Band DC, 所以可以匹配B D C

D B Z C F, 有Band C,F所以可以匹配B C F

D B Z D F, 有Band F, 所以可以匹配B F

…………

现在，我只是想suffix array。

1.首先将字符串转换为后缀数组对象。

2.循环每个模式，找到可以匹配的后缀数组。

3.比较所有匹配的模式，得到最好的模式。

我只是觉得这种方法很复杂，需要为模式构建一棵树，并用它来匹配后缀数组。谁有更多的想法？

=====================更新

我现在得到了一个最好的解决方案，我创建了一个新类，它有一个 B、C、D、X ......的属性是数组类型。每个属性保存一个出现在字符串中的位置。现在，如果字符串中没有出现B，我们可以立即结束这个处理。我们也可以得到所有的C和D位置，然后比较是否可以顺序出现(DC,DCC,CCC....)

我使用普林斯顿实现创建了一个后缀数组。但是，我的基本文本文档非常非常大，生成的后缀数组大小超过 500mb。有没有办法压缩后缀数组？

谢谢！

我根本找不到任何解释后缀数组的好的教学资源。甚至“圣经”也没有涵盖它。

我在哪里可以找到关于后缀数组及其用途的清晰透彻的解释？（视频课程是理想的，因为我很懒。）

解决这个问题的最佳方法（性能方面）是什么？我被推荐使用后缀树。这是最好的方法吗？

给定一个字符串 S，由小写拉丁字母组成。我想为每个位置 S[i] 最大长度 L[i] 找到一个位置 i' < i that s[i'..i'+L[i]-1] = s[i.. i+L[i]-1]。例如：s = ababaab，L= {0,0,3,2,1,2,1}。我想在 < O(|S|^2) 的时间内完成。我猜这个问题是用后缀数组解决的，但是如何解决呢？

我有一个后缀数组 SA 和一个数组 L 存储两个连续后缀之间的LCP（最长公共前缀）的长度，即

这里也有描述。

我应该如何使用这个数组 L 在给定的两个后缀 x 和 y 之间找到 LCP(x,y)？

假设我构造了一个后缀数组，即一个整数数组，它按字典顺序给出字符串所有后缀的起始位置。

示例：对于字符串str=abcabbca，

后缀数组是：

解释：

现在有了这个suffixArray构造，我想找到（字符串本身）和其他每个后缀之间的最长公共前缀（LCP）的长度。最有效的方法是什么？str

我只想知道，什么时候后缀树优于增强的后缀数组。

在阅读了用增强的后缀数组替换后缀树之后，我看不到使用后缀树的理由了。有些方法可能会变得复杂，但是您可以使用后缀数组来做所有事情，您可以使用后缀树来做任何事情，并且您需要相同的时间复杂度但更少的内存。

一项调查甚至表明，后缀数组更快，因为它们对缓存更友好，并且不会产生尽可能多的缓存未命中，然后是后缀树（因此缓存可以更好地预测数组使用情况，然后是递归树结构）。

那么，有谁知道选择后缀树而不是后缀数组的原因？

编辑 好的，如果您知道更多，请告诉我，到目前为止：

• 后缀数组不允许在线构建
• 一些模式匹配算法在后缀树上运行得更快
• （补充）由于在线构建，您可以将其保存在 hd a 并扩大现有的后缀树。如果您使用 SSD，它也应该很快安静。

这是 ACM ICPC 2003 的问题。其他用户已经在堆栈流中询问过这个问题。[但这没有用，我想通过后缀 Array 来解决。]

如何使用后缀数组来解决这个问题？

直到现在我做了什么？

(1) 假设给定的字符串是 S。

我将字符串 S 与自身连接起来得到一个字符串 S'。

IE。S'=S+S。

(2).然后我在O(nlog n )时间内找到了S'的后缀数组。

所以我很好地计算了后缀数组SA，SA[]={13,6,9,2,11,4,7,0,10,3,12,5,8,1}。

我还计算了每个后缀的 LCPs b/w [虽然我不相信我会在这个问题中需要它]。

现在如何进一步进行。如何使用 SA 来获得所需的结果？

用一个非常*小的例子来解释会非常有效。

谢谢！！