了解使用 LCP 阵列进行模式匹配的算法

Question

前言：我的问题主要是算法题，所以即使你不熟悉后缀和 LCP 数组，你也可以帮助我。

在 this 论文中描述了如何有效地使用后缀和 LCP 数组进行字符串模式匹配。

我了解 SA 和 LCP 的工作原理以及如何从 O(P*log(N)) 改进算法的运行时间（其中 P 是模式的长度，N 是字符串的长度）至 O(P+log(N))（感谢 Chris Eelmaa 的回答 and jogojapans answer here）。

我试图通过图 4 中的算法，它解释了 LLcp 和 RLcp 的用法。但是我无法理解它是如何工作的。

算法（取自the source）：

使用变量名说明：

lcp(v,w) : Length of the longest common prefix of v and w
W = w0..wP-1 : pattern of length P
A = a0..aN-1 : the text (length N)
Pos[0..N-1] : suffix array
L_W : index (in A) of first occurrence of the matched pattern
M : middle index of current substring
L : lower bound
R : upper bound
Lcp : array of size N-2 such that Lcp[M] = lcp(A_Pos[L_M], A_pos[M]) where L_M is the lower bound of the unique interval with M in the middle
Rcp : array of size N-2 such that Rcp[M] = lcp(A_Pos[R_M], A_pos[M]) where R_M is the upper bound of the unique interval with M in the middle

现在我想使用以下示例（部分摘自 here）尝试该算法：

 SA | LCP | Suffix entry
 -----------------------
 5  | N/A | a  
 3  | 1   | ana  
 1  | 3   | anana  
 0  | 0   | banana  
 4  | 0   | na  
 2  | 2   | nana 

A = "banana" ; N = 6
W = "ban" ; P = 3

我想尝试匹配一个字符串，比如 ban 并且期望算法 return 0 为 L_W.

下面是我将如何逐步完成算法：

l = lcp("a", "ban") = 0
r = lcp("nana", "ban") = 0
if 0 = 3 or 'b' =< 'a' then // which is NOT the case for both conditions
    L_W = 0
else if 0 < 3 or 'b' =< 'n' then // which is the case for both conditions 
    L_W = 6 // which means 'not found'
...
...

我觉得我错过了什么，但我找不到什么。另外我想知道如何使用预先计算的 LCP 数组而不是调用 lcp(v,w).

Answer 1

我认为有误。

第一个条件很容易理解。当 LCP 长度 == 模式长度时，它就完成了。当你的pattern甚至小于等于最小的时候，那就只能选择最小的了。

第二个条件错误。我们可以用反证法来证明。 r < P || Wr <= a... 意味着 r >= P && Wr > a... 如果 r >= P，那么我们怎么能有 Lw = N（未找到），因为我们已经有了 r 长度的公共前缀？

了解使用 LCP 阵列进行模式匹配的算法

Understanding the algorithm for pattern matching using an LCP array

algorithm

pattern-matching

suffix-array