了解 KMP 模式匹配算法中的特定细节-解网

问：

我有一个关于 KMP 模式匹配算法的问题。下面是用于计算数组的代码片段：next

int GetNext(char ch[], int length, int next[]) {
    next[1] = 0;
    int i = 1, j = 0;
    while (i < length) {
        if (j == 0 || ch[i] == ch[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

我对这段代码的原理理解如下：假设我们想要确定 next[j+1]，并且我们已经知道 next[1]、next[2],...下一页[J].如果 next[j] = p，则表示字符串第 j 个字符之前最长的公共前缀和后缀的长度为 p-1。如果字符串的第 j 个字符等于其第 p 个字符，则 next[j+1] = p+1。否则，我们需要考虑 next[p]，如果 next[p] = k，我们将字符串的第 j 个字符与其第 k 个字符进行比较。

我的问题是，我们为什么不将字符串的第 j 个字符与其第（p-1）个字符进行比较？我们怎么能确定将字符串的第 j 个字符与其第 p 个字符进行比较绝对不是正确的答案？例如，请考虑以下字符串（其中 S1 中的数字是索引）：

S1S2S3 S4S5S6 S7S8S9 S10 S11

使用上面的算法来计算next[11]，我们可以确定S1S2S3S4和S7S8S9S10是S11最长的公共前缀和后缀。我的问题是，我们怎么能确定这一点？我们如何确定 S1S2S3S4S5 和 S6S7S8S9S10 不是 S11 最长的通用前缀和后缀？

我想了解这个算法的细节;这个问题已经困扰了我一段时间

算法模式计算机科学字符串匹配

接下来意识到，由于是最大值，因此，如果，则为第二大值。我认为这是你缺少的部分。不能有这样的值。如果这些字符与以结尾的后缀匹配，那么它们也与以结尾的后缀匹配，我们将得到。next[b]IsPrefix(next[b], b)next[b] > 0next[next[b]]next[next[b]] < q < next[b]IsPrefix(q, b)qbnext[b]next[next[b]] = q

上一个：实际上，如何在函数中计算自动机然后返回它？

下一个：关于KMP模式匹配算法的问题

了解 KMP 模式匹配算法中的特定细节

Understanding a Specific Detail in the KMP Pattern Matching Algorithm

评论