nom*_*mad 11 algorithm pseudocode suffix-array
我正在看原始论文图3中给出的伪代码,它引入了后缀数组"SUFFIX ARRAYS:一种新的在线字符串搜索方法".
我无法弄清楚第4行和第5行的逻辑(从0开始索引).这些内容如下:
否则,如果 ř<P或瓦特 - [R ≤一个 POS [N-1] + R 然后
大号 W¯¯ ←Ñ
W是一个长度为"P"的,我们正在寻找和模式r是lcp(A[pos[N-1]:], W).问题是,在几乎所有情况下,这lcp将小于'W'的长度.这个条件是为了处理这种情况(我认为),该模式在字典上大于数组中按字典顺序排列的最大后缀,但它根本不测试这个.另一方面,第2和第3行测试是否W小于词典上最小的后缀似乎很有意义
如果升= P或瓦特升 ≤一个 POS [0] + 1 然后
大号 W¯¯ ←0
我相信原始的行应该是这样的:
否则如果 r <P且 w r > a Pos [N-1] + r 则
L W ←N.
唯一W可以大于A[pos[N-1]:]它的方式是它是否lcp比模式的长度短(否则,所有W匹配W都不能更大,只有更小或等于我们共享的东西lcp)和如果之后的字符lcp是更大的W比A[pos[N-1]].这看起来有意义吗？这是原始论文中的错误吗？如果没有,有人可以向我解释我是如何误解原始代码的吗？
小智 3
我认为你对这篇论文的理解是正确的，但实际上它有一个错误。
考虑以下示例：让A = banana, W = nana. 然后A[pos[N-1]:] = nana。算法设置LW = N甚至失败，而实际上它是N-1。