问题标签 [suffix-array]

我知道后缀数组本身的定义是它是一个字符串所有后缀的排序数组。但我想了解这里排序操作的意义是什么？假设我们创建了一个包含字符串所有后缀的数组并选择不对其进行排序并继续构建 LCP 数组，当我们尝试解决最长回文子字符串等常见问题时，我们在这种情况下会松动什么，最长重复子字符串？

我编写了一个 Suffix Array 实现并在我的实现中发现了一个问题。具体来说，我输出了RA[0..7]该字符串的前几个后缀数组等级（长度 = 10^5），并具有以下输出：

但正确的必须是（一切都移动了 23）：

我知道如何解决它的两种方法，但我不知道它为什么会起作用。

第一种方法是添加S[N++] = '$';到buildSA()函数的顶部（然后输出比正确的少1，但这没关系）

我还通过将 MAX_N 常数减小到 1e5 + 10 找到了另一种解决方案！

这对我来说太神奇了，我真的需要知道为什么会发生这个错误，因为我不想再次遇到这个错误。

有人可以向我解释一下后缀自动机到底是什么，它是如何工作的以及与后缀树和后缀数组的区别？我已经尝试在网上搜索，但无法找到任何清晰全面的解释。

我发现以下链接最接近我想要的，但它是俄文的，翻译成英文很难理解。

http://e-maxx.ru/algo/suffix_automata

我正在查看示例后缀数组和最长公共前缀，但我不了解后缀数组如何排序的标准。我正在查看维基百科上他们使用香蕉$ 的示例，有人可以解释一下后缀数组是如何排序的吗？我的第一直觉是按长度排序，但这里显然不是这样。

（这是他们使用的示例http://en.wikipedia.org/wiki/Suffix_array）

这些后缀可以排序：

给定一个后缀数组，来自 SRM 630 的 TopCoder 任务要求找到字符串中可以形成具有给定后缀数组的字符串的最小数量的不同字符。完整的问题陈述可以在 TopCoder 网站上找到。

我找到的最佳解决方案就在这里：https ://github.com/ftiasch/acm-icpc/blob/6db1ed02a727611830b974a1d4de38bab8f390f9/topcoder/single-round-match/single-round-match-630/SuffixArrayDiv1.java

这是ftiasch写的算法：

我知道这是一种动态编程算法，但它是如何工作的？我真的需要一只手来理解它。

编辑

以下是 ftiasch 给我的回信：

嗨，爱丽儿，

首先感谢您的夸奖。坦率地说，我的解决方案并不是解决问题的最佳方案。最佳的运行时间为 O(n)，但我的运行时间为 O(n^4)。我只是在比赛中选择了这个想法，因为 n 相对较小。

请记住，相同的字符在 SA 中变得连续。由于问题要求字符数最少，所以我决定使用动态编程将 SA 划分为连续的段，以便每个段以相同的字符开头。

假设 i < j，S[SA[i]] == S[SA[j]] 的必要条件是什么？字典比较表明 suffix(SA[i] + 1) 应该小于 suffix(SA[j] + 1)。我们不难发现，条件也是充分的。

如果您有任何其他问题，请写信给我。:)

编辑1

感谢大卫，我们终于成功了。这是来自 David 的 Python 版本的 java 中的线性时间算法：

我也在阅读来自 codechef 和 stackoverflow 的后缀数组构造教程。我能理解的一点是他们说..

它的工作原理是首先对原始字符串 S 的 2-grams(*)、4-grams、8-grams 等进行排序，所以在第 i 次迭代中，我们对 2i-grams 进行排序

等等。每次迭代 i 有两个步骤：

按 2i-gram 排序，使用上一次迭代中的词典名称，以便在 2 个步骤（即 O(1) 时间）中进行比较

创建新的词典名称

我的疑问是：如何使用以 2 克计算的索引为 4 克。?

假设我的 2 个后缀是“ab”、“ac”，那么您如何在 O(1) 时间内进行比较并为它们提供索引。

我真的试过但卡在那里。请提供一些例子，这会有所帮助。提前致谢

我试图了解 Karkkainen，P. Sanders 的线性时间后缀数组创建算法的实现。可以在此处找到算法的详细信息。

我设法理解了整体概念，但未能将其与提供的实现相匹配，因此无法清楚地掌握它。

这是让我感到困惑的初始代码路径。

根据论文：n0、n1、n2 表示从 i mod 3 = (0,1,2) 开始的三元组数

根据代码：n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3; => 这些初始化是如何得出的？

根据论文：我们需要创建 T`，它是 i mod 3 处三元组的串联！= 0

根据代码：n02 = n0 + n2; s12 = [n02] ==> n02 怎么来的？它应该是 n12 即 n1 + n2。

根据代码： for (int i = 0, j = 0; i < n + (n0 - n1); i++) 用三元组填充 s12，使得 i%3 != 0; => 为什么 for 循环运行 n + (n0 - n1) 次？它应该是简单的 n1 + n2。不应该吗？

由于这些原因，我无法继续:(请帮忙。

我正在查看原始论文的图 3 中给出的伪代码，其中介绍了后缀数组"SUFFIX ARRAYS: A NEW METHOD FOR ON-LINE STRING SEARCHES"。

我无法弄清楚第 4 行和第 5 行的逻辑（从 0 开始索引）。行内容如下：

否则，如果r < P或w _r ≤ a _Pos[N-1]+r 则
L _W ← N

W是我们正在寻找的长度为 'P' 的模式并且r是lcp(A[pos[N-1]:], W). 问题是在几乎所有情况下，这lcp将小于“W”的长度。这个条件是为了处理这种情况（我认为）模式在字典上大于数组中字典上最大的后缀，但它根本不测试这一点。另一方面，测试是否W小于字典最小后缀的第 2 行和第 3 行似乎很有意义

如果l = P或w _l ≤ a _Pos[0]+l 则
L _W ← 0

我相信原来的行应该是这样的：

else if r < P and w _r > a _Pos[N-1]+r then
L _W ← N

唯一W可以大于的方法A[pos[N-1]:]是它的lcp长度小于模式的长度（否则，所有W匹配项W都不能大于，只能小于或等于我们共享的对象lcp）并且如果in之后的字符lcp大于Win A[pos[N-1]]。这似乎有意义吗？这是原始论文中的错误吗？如果没有，有人可以向我解释我是如何误解原始代码的吗？

我通过实现后缀数组时不断收到编译器错误Arrays.sort。

我收到以下错误：

a 无法解析为
标记 ",", 上的变量语法错误。
标记“-”上的预期语法错误，- 预期
a 无法解析为变量
b 无法解析为变量

在以下代码中：

有人可以解释一下 e-maxx.ru 页面中给出的后缀数组构造算法的工作原理吗

我无法理解它的代码

一个小例子的解释可能非常有效

链接：http ://e-maxx.ru/algo/suffix_array