问题标签 [suffix-array]

我正在开发一个程序来查找多个字符串之间最长的公共子字符串。我已经降低了使用后缀数组或后缀树的方法。我想看看哪种方法更好（如果有的话）以及为什么。同样对于后缀数组，我已经看到了一些针对两个字符串的算法，但对于两个以上的字符串却没有。任何可靠的例子将不胜感激，再次感谢您的建议！

注意：我没有看到任何其他专门解决此问题的问题，但如果存在，请指出我的方向！

我正在阅读关于后缀数组的原始论文，并最终计划基于此自己实现它，但是有一行伪代码我不确定如何解释并且无法通过搜索找到任何内容任何能用英语解释它在说什么的人都会感激不尽。

L _w = min(k:W ≤<sub>p A _pos[k]或 k=N)

其中 k 是某个整数，W 是一个字符串，≤<sub>p 表示使用字典顺序进行比较，A _pos[k]是 A 的第 k^个最小后缀的位置，N 是 A 的长度。谢谢。

要在 n 个字符的字符串上构建一个 suffis 数组，

1. 我们首先生成 n 个后缀 O(n)
2. 然后对它们进行排序 O(n log n)

总时间复杂度似乎是 O(n) + O(nlogn) = O(nlogn)。

但我读到它是 O(n^2 log n) 并且无法理解。有人可以解释一下吗？

我们有两个字符串a和b分别。的长度a大于或等于b。我们必须找出最长的公共子串。如果有多个答案，那么我们必须输出较早出现的子字符串b（早于其起始索引在前）。

注意：a和的长度b最大为 10 ⁶。

我尝试使用后缀数组查找最长的公共子字符串（使用快速排序对后缀进行排序）。对于有多个答案的情况，我尝试将所有公共子字符串推入堆栈中，这些子字符串等于最长公共子字符串的长度。

我想知道有没有更快的方法呢？

我正在使用这个程序来计算后缀数组和最长公共前缀。

我需要计算两个字符串之间的最长公共子字符串。

为此，我连接字符串，A#B然后使用这个算法。

我有后缀数组sa[]和LCP[]数组。

LCP[]最长的公共子串是数组的最大值。

为了找到子串，唯一的条件是在相同长度的子串中，字符串B中第一次出现的那个应该是答案。

为此，我维持 LCP[] 的最大值。如果LCP[curr_index] == max，那么我确保left_index子字符串 B 的 小于 的先前值left_index。

但是，这种方法并没有给出正确的答案。错在哪里？

如何计算后缀数组的 LCP 数组？它不一定是最有效的。O(n log n) 或 O(n) 都可以。如果可能的话，一些相对容易编码的东西。

我曾经根据我的需要使用动态编程O(m * n)、后缀树O(m + n)、后缀数组O(nlog^2 n)来计算最长公共子串。最近我学习了Suffix Automaton，它在O(n)中的表现非常令人印象深刻。

我可以编写可以轻松计算最长公共子串长度的代码。例如：

这是代码：

但现在我需要打印最长的公共子字符串本身，而不是长度。但是我无法修改我的代码:(如何修改此代码以打印最长的公共子字符串？

假设给我一个字符串 S。

我需要找到包含 S1 作为前缀和 S2 作为后缀的 S 的不同子字符串的数量。

S、S1、S2的范围可以很大，即O(10^5)。

例如。

假设 S 是“abcdcd”，S1 是“ab”，S2 是“cd”。

“ababcdcd”的不同子串是：“a”、“b”、“c”、“d”、“ab”、“bc”、“cd”、“dc”、“abc”、“bcd”、“ cdc”、“dcd”、“abcd”、“bcdc”、“cdcd”、“abcdc”、“bcdcd”、“abcdcd”。使用 Suffix Array 可以轻松找到不同子串的总数。我正在尝试扩展相同的想法来解决问题。

在这些子串中，包含“ab”作为前缀和“cd”作为后缀的子串是：“abcd”、“abcdcd”。

因此答案是2。

PS：我相信它使用后缀数组，但我不确定如何。请帮忙。

需要为每个数组成员添加相同的后缀 (.wav)，如下所示：

所需输出：

我试图通过以下方式实现这一目标：

但我失败了。我应该怎么做才能达到所需的输出？

我正在尝试在大文本中查找包含子字符串（作为输入）的单词。文本如下所示：*america*python*erica*escape*.. 示例：输入：“rica” => 输出：america,erica

我使用后缀数组。

我的伪代码（pythonlike）是：

这行得通，但是太慢了。LCP 阵列应该改善算法的运行时间，但我不知道如何。你能给我一个建议吗？

提前致谢！