问题标签 [suffix-array]

Can someone explain how this code for constructing the LCP from a suffix array works? suffixArr[] is an array such that suffixArr[i] holds the value of the index in the string for the suffix with rank i.

我的代码正确计算了间隔的起始位置，但没有计算结束位置：

我将它与互联网上的几个伪代码进行了比较，我真的不明白为什么它不起作用。我错过了什么？

I'm really trying to understand an example on how to construct a good suffix table for a given pattern. The problem is, I'm unable to wrap my head around it. I've looked at numerous examples, but do not know where the numbers come from.

So here goes: The following example is a demonstration of how to construct a Good Suffix Table given the pattern ANPANMAN:

Any help on this matter is highly appreciated. I simply don't know how to get to these numbers. Thanks!

我想建立一个通用的后缀树。我正在使用http://www.daimi.au.dk/~mailund/suffix_tree.html进行此实现。我的代码如下：

对于 x = 35 的值，代码工作正常，但对于 x = 36 或更多，我得到以下错误

例外来自此文件https://github.com/Yacoby/suffix-tree-unicode/blob/master/suffix_tree.py

我不明白为什么它适用于值 x < 36 但不适用于其他值。请帮助我了解这里发生了什么。

我试图弄清楚如何在后缀数组中进行二进制搜索以查找一次模式的出现。让我们有一个文本：。我试图找到.petertomasjohnerrnoerrorer

SA是此文本的后缀数组：8,14,19,3,1,12,10,7,13,17,18,11,6,22,0,23,16,21,15,20,4,9,2,5

现在，我想找到后缀数组的任何索引，它的值指向一个'er'. 所以输出将是 SA 中指向的索引，3,14 or 19因此它将返回 1,2 或 3

我正在尝试使用二进制搜索，但我不知道如何。

这返回11。但text[SA[11]:SA[11]+2]不是。'oh'_ 'er'问题可能出在哪里？

此功能适用于大约数百万个字符的大量文本。

编辑：我发现了一个错误。而不是 if text[SA[check]:SA[check+len(p)]]<p:should betext[SA[check]:SA[check]+len(p)]<p:但它仍然是错误的。它返回 None 而不是'er'

编辑二：另一个错误：如果 high>=low 更改为 high<=low，现在它返回 2，这很好。

编辑三：现在它可以工作了，但是在某些输入上它会进入循环并且永远不会结束。

你好这里是问题。

1. 检查 s1 是否具有前缀 AAA 并将结果分配给布尔变量 b

2. 检查 s1 是否具有前缀 AAA 并将结果分配给布尔变量 b

这是我到目前为止所拥有的

真的停留在这一点上，头脑已经一片空白。所以帮助将不胜感激

我构造了一个由 ArrayList 实现的后缀数组。

我想使用这个列表来搜索后缀数组中的后缀。为此，我对列表进行了排序并使用了二进制搜索，但“搜索”函数不断返回 -1

我不知道我在这里做错了什么。我也覆盖了 Hashcode 和 equals 。

我还更改了“等于”的默认定义，但我仍然得到相同的输出

Foreword: My question is mainly an algorithmic question, so even if you are not familiar with suffix and LCP arrays you can probably help me.

In this paper it is described how to efficiently use suffix and LCP arrays for string pattern matching.

I understood SA and LCP work and how the algorithm's runtime can be improved from O(P*log(N)) (where P is the length of the pattern and N is length of the string) to O(P+log(N)) (Thanks to Chris Eelmaa's answer here and jogojapans answer here).

I was trying to go through the algorithm in figure 4 which explains the usage of LLcp and RLcp. But I have problems understanding how it works.

The algorithm (taken from the source):

Explanation of the used variable names:

Now I want to try the algorithm using the following example (partly taken from here):

I want to try to match a string, say ban and would expect the algorithm to return 0 as L_W.

Here is how I would step through the algorithm:

I feel like I am missing something but I can't find out what. Also I am wondering how the precomputed LCP array can be used instead of calling lcp(v,w).

做一个练习CheckIO，我想知道为什么这不起作用。给定一组字符串，如果任何字符串是集合中任何其他字符串的后缀，我将尝试返回 True。否则为假。使用 itertools 我首先在元组中生成必要的排列。然后对于每个元组（每个 i），我想看看第二个元组是否在第一个元组的末尾（选项 1）。另一种方法是使用 .endwith 函数（选项2），但两者都不适合我。为什么这两个选项有缺陷？

例子：

我知道这可以作为答案。但只是想知道为什么我原来的方法不会采用。

今天我正在尝试使用 scala 创建后缀数组。我能够使用大量代码行来完成它，但后来我听说它可以通过使用压缩和排序仅使用几行代码来创建。

我现在遇到的问题是一开始。我尝试使用二进制搜索和 zipWithIndex 来创建以下“树”，但到目前为止我还无法创建任何东西。我什至不知道仅使用一条线是否有可能，但我敢打赌它是大声笑。

我想做的是从“芝士蛋糕”这个词中得到一个Seq：

有人可以将我推向正确的道路吗？