2

为 KMP 构建部分匹配表时：

void buildBackTable() { 
    int i = 0, j = -1; b[0] = -1; 
    while (i < m) { 
        while (j >= 0 && P[i] != P[j]) j = b[j]; //Why is this a while loop!?
        i++; j++;
        b[i] = j;
    }
}

为什么第二个 while 循环不是有条件的呢？如：

void buildBackTable() { 
    int i = 0, j = -1; b[0] = -1; 
    while (i < m) { 
        if (j >= 0 && P[i] != P[j]) j = b[j]; //Why not?
        i++; j++;
        b[i] = j;
    }
}

在我尝试过的大多数示例中，此语句用于在不匹配时将 j 重置为 -1，因此当下一次迭代到来时，我们将字符串的第一个字符 (P[j]) 与该字符进行比较在位置 i (P[i])。

4

1 回答 1

1

首先澄清一下，在 OP 的符号中m代表 string 的长度P。注意b是长度m+1。（这是其中一种实现方式，尽管就符号而言，这可能不是最自然的，这可能会引起混淆）

让我们看看它buildBackTable()的目的是什么。本质上，对于产生的数组b，b[i]将存储最大值j，例如j < i, 和P[0..j-1] == P[i-j..i-1], b[0]=-1。

理解以下属性并不难：

  1. b[i] <= b[i-1] + 1
  2. 如果b[i] = j，那么对于任何k < j， st P[0..k-1] == P[i-k..i-1]，我们都知道b[j] >= k。同时，显然b[i] > b[j]或b[i] = 0。

这意味着我们可以通过遍历等轻松地k从最大到最小枚举值b[i] -> b[b[i]] -> b[b[b[i]]]...。

这个枚举允许我们跳过 的前缀P并找到最大值jstP[0..j-1] == P[i-j..i-1]和P[i] == P[j]。

至于你的问题，当条件检查（没有循环失败）时，只需考虑字符串aaaac。然后b[4] = 3。但是b[5] = 0。只有条件检查，你会得到b[5]=3.

于 2016-08-05T04:11:27.640 回答