问题标签 [suffix-array]

我读过最长公共前缀（LCP）可用于查找字符串中模式的出现次数。

具体来说，您只需要创建文本的后缀数组，对其进行排序，然后无需进行二进制搜索来查找范围以便计算出现次数，您只需计算文本中每个连续条目的 LCP后缀数组。

尽管使用二进制搜索来查找模式的出现次数是显而易见的，但我无法弄清楚 LCP 如何帮助在这里找到出现次数。

例如对于这个后缀数组banana：

LCP 如何帮助找到像“banana”或“na”这样的子字符串的出现次数对我来说并不明显。

任何帮助弄清楚 LCP 如何在这里提供帮助？

对于以下问题，我很难找到比 O(n^2) 更好的方法。

我得到一个字符串，例如xyxxz.

现在我需要在给定字符串的每个前缀中找到匹配字符的总数。

在这里，字符串的可能前缀是：

这应该是输出。我做了以下代码：

但它是 O(n^2)。我想要一个更好的方法：可能是 O(n) 或 O(nlogn)。

提前致谢。

请解释：

假设我们有一个对应于一个 n 字符文本的后缀数组，并且我们想要在一个 m 字符模式的文本中查找所有出现。由于后缀是有序的，最简单的解决方案是使用 O(log n) 比较对模式的第一次和最后一次出现（如果有）进行二进制搜索。

在确定 pattern 的第一次和最后一次出现后，我需要知道如何获得所有出现的 pattern。

我们可以使用带有后缀链接的因子-oracle（此处为论文）来计算多个字符串的最长公共子字符串吗？这里，子字符串表示原始字符串的任何部分。例如“abc”是“ffabcgg”的子字符串，而“abg”不是。

我找到了一种方法来计算两个字符串的最大长度公共子字符串s1和s2. 它通过使用不在其中的字符连接两个字符串来工作，例如'$'。s然后对于长度为 的连接字符串的每个前缀i >= |s1| + 2，我们计算其 LRS（最长重复后缀）长度lrs[i]和sp[i]（其 LRS 第一次出现的结束位置）。最后，答案是

我已经编写了一个使用这种方法的 C++ 程序，它可以在我的笔记本电脑上|s1|+|s2| <= 200000使用因子 oracle 在 200 毫秒内解决问题。

我知道使用 suffix-array 和 suffix-tree 可以高效地解决这两个问题，但是我想知道是否有使用因子 oracle 的方法来解决它。我对此感兴趣是因为因子 oracle 很容易构造（用 30 行 C++，suffix-array 需要大约 60，而 suffix-tree 需要 150），并且它比 suffix-array 和 suffix-tree 运行得更快。

您可以在此 OnlineJudge中测试您的第一个问题的方法，并在此处测试第二个问题。

我们需要找到两个字符串之间的最短不常见子字符串，即如果我们有两个字符串a，b那么我们需要找到a不是 的子字符串的最短子字符串的长度b。

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

以不超过 n*lg(n) 的复杂度求解

我需要在字符串中找到最长的非重叠重复子字符串。我有可用的字符串的后缀树和后缀数组。

当允许重叠时，答案很简单（后缀树中最深的父节点）。

例如对于 String = "acaca"

如果允许重叠，则答案为“aca”，但不允许重叠时，答案为“ac”或“ca”。

我只需要算法或高级想法。

PS：我试过了，但在网上找不到明确的答案。

考虑一个长度为 n (1 <= n <= 100000) 的字符串。确定其最小字典旋转。例如，字符串“alabala”的旋转是：

这个问题已经在 Stack 上被问过，但我正在问它，因为没有明确的解决方案可用。到目前为止，我取得了以下进展。
1.取S，concat with reverse(S)..let P=S+reverse(S)
2.构造上述字符串P的后缀数组

现在我的问题是如果我选择后缀数组中的第一个字符串size> strlen(S)那么这个字符串大小strlen(S)的前缀将是给定字符串 S 的最小旋转。

我的结论正确吗？

在“Programming Pearls”：Strings of Pearls，第 15.3 节（生成文本）中，作者介绍了如何从输入文档中生成随机文本。在源代码中，有一些我不明白的东西。

作者解释说：“在读取输入后，我们附加了 k 个空字符（因此比较函数不会跑到最后）。” 这个解释真的让我很困惑，因为在评论这两行之后它仍然很好用。为什么这是必要的？

我必须从大型 PDF 文档中构建某种“字符串目录”，以便更快地搜索字符串/子字符串。

该机制应该像这样工作：PDF 扫描仪扫描 PDF 文档中的字符串，并在我的目录中调用回调方法来索引该字符串。

现在，应该使用什么技术来构建这样的目录？我听说过： - 后缀树 - 广义后缀树 - 后缀数组

我主要倾向于广义后缀树。那我是对还是错？我猜“普通”后缀树只适用于索引单个字符串。

但是后缀数组呢？那里有通用的后缀数组吗？

我在 C/C++ 中发现了很多用于从字符串构建后缀树的代码，但没有用于构建通用后缀树的代码！

我正在寻找一种有效的数据结构来对一组非常庞大的字符串进行字符串/模式匹配。我发现了尝试、后缀树和后缀数组。但是到目前为止，我在 C/C++ 中找不到一个现成的实现（而且我自己实现它似乎很困难并且容易出错）。但我仍然不确定 Suffix-Arrays 是否真的是我正在寻找的东西......我已经尝试过 libdivsufsort 和 esaxx，但无法找到如何使用它们来满足我的需求：

我想使用一组预定义的字符串，带有通配符（甚至是正则表达式）来匹配用户输入。我有一大堆预定义的字符串，即

“什么是 *？” “什么是 XYZ？” “多少 *？” ...

现在我想找到最匹配的字符串（如果有的话，那就完全匹配了）。即用户输入：>什么是XYZ？应该找到“什么是 XYZ？” 而不是“什么是*？”，而是“什么是什么？” 应该找到“什么是*？” （假设 * 是任何字符数的通配符）。

构建结构不是时间紧迫的（并且结构不必非常节省空间），但搜索不应该花费太长时间。怎么能轻易做到呢？欢迎任何框架/库或代码示例

谢谢