后缀数组算法
经过一番阅读，我弄清楚了后缀数组和LCP数组的含义。 后缀数组：表示一个数组中每个后缀在字典序中的排名。 LCP数组：包含经过字典序排序后，相邻两个后缀之间的最长公共前缀长度。 我已经努力尝试理解后缀数组和LCP算法是如何工作的，并花费了几天时间。 下面是来自Codeforces的代码...
目前最先进的后缀数组构建算法是什么？
我正在寻找一种快速的后缀数组构建算法。我更关心实现的简便和原始速度，而不是渐近复杂度（我知道后缀数组可以通过后缀树以O(n)的时间构建，但那需要很多空间；显然其他算法具有糟糕的最坏情况下的大O复杂度，但在实践中运行得非常快）。我不介意算法生成一个LCP数组作为副产品，因为我需要它来满足我的需求...
LCP如何帮助找到一个模式的出现次数？
我已经阅读了关于“最长公共前缀（LCP）”可以用来在字符串中查找模式出现次数的方法。 具体来说，您只需要创建文本的后缀数组，对其进行排序，然后不是执行二进制搜索以查找范围以便您可以确定出现次数，而是计算每个后缀数组条目的LCP。 尽管使用二分搜索来查找模式出现次数很明显，但我无法理解LCP...
后缀数组 vs 后缀树
我只是想知道，在何时后缀树比增强型后缀数组更优。 在阅读了Replacing suffix trees with enhanced suffix arrays之后，我不再看到使用后缀树的理由。有些方法可能会变得复杂，但你可以用一个后缀数组做到与使用后缀树相同的操作，且时间复杂度相同但占用更少的内...
使用后缀树/数组求最长的不重叠的重复子字符串（仅算法）
我需要找到一个字符串中最长的非重叠重复子串。我的字符串有后缀树和后缀数组可用。 当允许重叠时，答案是显而易见的（后缀树中的深度最大父节点）。 例如对于字符串“acaca” 如果允许重叠，则答案是“aca”，但当不允许重叠时，答案是“ac”或“ca”。 我只需要算法或高层次思路。 P....
如何在块排序中对数组后缀进行排序
我正在阅读Burrows和Wheeler论文中的块排序算法。 这是算法的一步： 初始化一个由N个单词W[0, ... , N - 1]组成的数组W，使得W[i]包含字符S'[i, ... , i + k - 1]，这些字符被排列在一起，以便单词的整数比较与k个字符字符串的字典比较相符。将字符打...
后缀数组 nlogn 创建
我一直在学习后缀数组的创建，我了解到我们首先按第一个字符、然后按前两个字符排序，接着按前四个字符排序，当要考虑的字符数小于2n时，再按此方式排序。 但我的疑问是为什么我们不选择前三个字符，然后是9个字符...以此类推。既然字符串属于同一个字符串而不是不同的随机字符串，为什么只考虑两个字符呢？
Python中寻找最长重复字符串的高效方法（来自《编程珠玑》）
来自《编程珠玑》第15.2节 这里可以查看C代码：http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c 当我使用后缀数组在Python中实现时：example = open("iliad10.txt").read() def comlen(p...
原始论文中后缀数组存在勘误？
我在研究介绍后缀数组的原始论文中给出的伪代码，它位于第3个图表中 "SUFFIX ARRAYS: A NEW METHOD FOR ON-LINE STRING SEARCHES"。 我无法理解第4和第5行的逻辑（从0开始索引）。 这两行代码如下： else if r < P or...