0

我在 CLRS 自学问题 32-1；c) 部分介绍了以下字符串匹配算法：

REPETITION-MATCHER(P, T)
  m = P.length
  n = T.length
  k = 1 + ρ'(P)
  q = 0
  s = 0
  while s <= n-m
    if T[s+q+1] == P[q+1]
      q = q+1
      if q==m
        print "Pattern occurs with shift" s
    if q==m or T[s+q+1] != P[q+1]
       s = s+max(1, ceil(q/k))
       q = 0

这里，ρ'(P)，它只是 P 的函数，被定义为最大整数 r，使得某个前缀 P[1..i] = y^r，例如重复 r 次的子串 y。

该算法似乎与简单的暴力字符串匹配器有 95% 的相似性。然而，让我非常困惑的一个部分，似乎是整个算法的核心，是倒数第二行。这里，q 是到目前为止匹配的 P 的字符数。背后的原理是ceil(q/k)什么？这对我来说是完全不透明的。如果该行类似于s = s + max(1+q, 1+i)，那将更有意义，其中 i 是产生 ρ'(P) 的前缀的长度。

CLRS 声称该算法归功于 Galil 和 Seiferas，但在他们提供的参考资料中，我找不到与上面提供的算法相似的任何东西。如果有的话，参考似乎包含这里的更高级版本。有人可以解释这个ceil(q/k)值，和/或指向描述这个特定算法的参考，而不是更知名的主要 Galil Seiferas 论文吗？

4

2 回答 2

0

我想出了正确性的证明。

令 k = ρ'(P) + 1，ρ'(P) 是 P 的所有前缀中最大可能的重复因子。

假设T[s+1..s+q] = P[1..q],q=m或者T[s+q+1] != P[q+1]

然后，对于 1 <= j <= floor(q/k)（除了 q=m 和 m mod k = 0 的情况，其中上限必须为 ceil(m/k)），我们有

T[s+1..s+j] = P[1..j]
T[s+j+1..s+2j] = P[j+1..2j]
T[s+2j+1..s+3j] = P[2j+1..3j]
...
T[s+(k-1)j+1..s+kj] = P[(k-1)j+1..kj]

其中不是每行上的每个数量都是相等的，因为 k 不能是重复因子，因为 P 的任何前缀中最大可能的重复因子是 k-1。

假设我们现在在 shift s' = s+j 处进行比较，那么我们将进行以下比较

T[s+j+1..s+2j] with P[1..j]
T[s+2j+1..s+3j] with P[j+1..2j]
T[s+3j+1..s+4j] with P[2j+1..3j]
...
T[s+kj+1..s+(k+1)j] with P[(k-1)j+1..kj]

我们声称并非每个比较都可以匹配，例如，上述“with”中的至少一个必须替换为 !=。我们用反证法来证明。假设上面的每个“with”都被 = 代替。然后，与我们所做的第一组比较相比，我们将立即得到以下结果：

P[1..j] = P[j+1..2j]
P[j+1..2j] = [2j+1..3j]
...
P[(k-2)j+1..(k-1)j] = P[(k-1)j+1..kj]

然而，这不可能是真的，因为 k 不是重复因子，因此是矛盾的。

因此，对于任何 1 <= j <= floor(q/k)，测试一个新的班次 s'=s+j 保证不匹配。

因此，可能导致匹配的最小偏移是 s + floor(q/k) + 1 >= ceil(q/k)。

请注意，代码使用 ceil(q/k) 为简单起见，仅用于处理 q = m 和 m mod k = 0 的情况，在这种情况下 k * (floor(q/k)+1) 将大于 m ，所以只有 ceil(q/k) 会做。然而，当 q mod k = 0 且 q < m 时，ceil(q/k) = floor(q/k), 所以稍微次优，因为该移位肯定会失败，并且 floor(q/k)+1是有任何匹配机会的第一个班次。

于 2018-01-20T01:30:41.390 回答
0

示例 #1：aaaa在aaaaab此处 匹配ρ' = 4。考虑状态：

aaaa ab
    ^

我们这里有一个不匹配，我们想要向前移动一个符号，不再，因为我们将再次匹配完整模式（最后一行设置q为零）。q = 4和k = 5，所以ceil(q/k) = 1，没关系。

示例 #2：匹配abcd.abcd.abcd.X. abcd.abcd.abcd.abcd.X考虑状态：

abcd.abcd.abcd. abcd.X
               ^

我们这里有一个不匹配，我们想向前移动五个符号。q = 15和k = 4，所以ceil(q/k) = 4。没关系，快 5 了，我们仍然可以匹配我们的模式。如果我们更大ρ'，比如说 10，我们就会有ceil(50/(10+1)) = 5。

是的，算法跳过的符号比 KMP 少，以防ρ'=10它的运行时间是O(10n+m)KMP 有O(n+m).

于 2018-01-19T14:13:38.360 回答