我在研究介绍后缀数组的原始论文中给出的伪代码,它位于第3个图表中 "SUFFIX ARRAYS: A NEW METHOD FOR ON-LINE STRING SEARCHES"。
我无法理解第4和第5行的逻辑(从0开始索引)。 这两行代码如下:
else if r < P or wr ≤ aPos[N-1]+r then
LW ← N
W
是长度为'P'的匹配模式,而r
是lcp(A[pos[N-1]:], W)
。问题在于,在几乎所有情况下,这个lcp
都会小于'W'的长度。这个条件语句的意思是处理这种情况的(我想),即模式在数组中按字典顺序比最大后缀要大,但它并没有进行任何测试。另一方面,第2和第3行则测试W
是否小于按字典顺序最小的后缀,这似乎是有道理的。
如果 l = P 或者 wl ≤ aPos[0]+l 那么
LW ← 0
我认为原来的代码应该像这样:
否则如果 r < P 且 wr > aPos[N-1]+r 那么
LW ← N
唯一的可能是当W
具有比模式长度更短的lcp
时(否则,所有的W
都匹配,所以W
不能更大,只能小于或等于我们正在共享的那个东西的lcp
)lcp
后的字符在W
中大于A[pos[N-1]]
中的字符。这听起来有道理吗? 这是原始论文中的错误吗?如果不是,请有人告诉我我是如何误解原始代码的?