KMP算法重点讲k=next[k]-一一网

看了很多文章, 一旦涉及到getNext中的k=next[k]时, 很多文章就是一笔带过, 或者不少文章都会讲终于搞懂了KMP算法, 但是到这里还是一笔带过, 越看越懵逼。
这篇笔记重点讲k = next[k]这个逻辑, 其他的地方假设你已经搞懂了。

笔记写完了, 但是发现好像只有我自己看得懂, 好尴尬, 如果你看到最后还是觉得模模糊糊, 不妨自己画个图试试, 如果还是不明白K = next[K], 可以私聊一起探讨。

public static int KMP(String ts, String ps) {
    char[] t = ts.toCharArray();
    char[] p = ps.toCharArray();
    int i = 0, j = 0;
    int[] next = getNext(ps);
    while (i < t.length && j < p.length) {
        if (j == -1 || t[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == p.length) {
        return i - j;
    }
    return -1;
}

/**
 * ABCDEEEEEABCEABCDEEEEEABCF
 * ABCDEEEEEABCD
 *   A  B  C  D  E  E  E  E  E  A  B  C  D
 * [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3]
 */
public static int[] getNext(String ps) {
    char[] p = ps.toCharArray();
    int[] next = new int[p.length];
    int j = 0, k = -1;
    next[0] = -1;
    while (j < p.length - 1) {
        if (k == -1 || p[j] == p[k]) {
            // 这里有一个优化的点, 但是这里只写最原始的代码, 如何优化可以参考其他文章
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
    System.out.println("next = " + Arrays.toString(next));
    return next;
}
复制代码

先说几个结论:

先说几个结论, KMP的设计思路除了getNext之外, 假设你已经懂了。
对于主串char[] t, 子串char[] p

1、next[j]: 表示当p[j] != t[j]时, p串前后缀相等的最大长度。
2、next[j] = -1: 表示主串和子串均需要右移

结合这两个结论来分析getNext方法

getNext数组求解过程

public static int[] getNext(String ps) {
    char[] p = ps.toCharArray();
    int[] next = new int[p.length];
    int j = 0, k = -1;
    next[0] = -1;
    while (j < p.length - 1) {
        if (k == -1 || p[j] == p[k]) {
            // 这里有一个优化的点, 但是这里只写最原始的代码, 如何优化可以参考其他文章
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
    System.out.println("next = " + Arrays.toString(next));
    return next;
}
复制代码

看了很多文章, 都在讲核心就是k = next[k], 都说这个地方是核心, 但是却都选择一笔带过, 学习KMP时浪费了大量的时间在无用的文章上面。

1、分析流程

1、p[j] == p[k]
2、k = next[k];
3、k == -1;

2、p[j] == p[k]

当p[J0] != t[i] && p[J0] = p[K0], j0点对应的相等前后缀的最大长度为K0, 也就是说next[J0] = K0;
那么此时是不是有next[J1] = K1呢?

推导公式就是:
P[J0] == P[K0], next[J0] == K0
推导出===> next[J1] == K0 + 1 == K1;
复制代码

3、K = next[K]

第一个公式很简单, 就是顺时+1, 这里K = next[K]这个就容易比较让人懵逼了, 我觉得这里应该用的是完全归纳法得出来的结论, 恰好这里又把完全归纳法的过程给省略了…

所以这里如果不讲完全归纳法, 就很难搞懂这一块儿

结合公式二的流程:
(1) 假设next[J0] = K0 && P[J0] == P[K0], 那么此时有next[J1] == K0 + 1 == K1
(2) 以此类推, 如果P[J1] == P[K1], 那么得出 next[J2] = K1 + 1 = K2;
如下图所示, 直接顺时推导出K2的位置, 依次求得next[J1...JN]的值
复制代码

如果P[J1] != P[K1]

那么如果当P[J1] != P[K1]时, 接下来应该如何操作才能正确的计算出next[J2]呢???

此时需要将K1进行左移, 直到找到K3保证P[J1] == P[K3], 此时next[J2] == K3

开始推导K = next[K]公式:
(1) K1左移得到J2的最长公共前后缀K3节点, 此时有next[J2] = K3, P[0 ~ K3-1] == P[ J1-K3+1 ~ J1]
(2) 也就是P[J1] == P[K3 - 1], P[J0] == P[K3 - 2]...
(3) 咱们还记得之前的P[J0] == P[K0]吗?
(4) 根据(3)得出:  P[K0] == P[K3 - 1]
(5) 步骤(2)和步骤(4)是不是一模一样的? 结合K3 < K1, 且P[K0] == P[K3 - 1], 
    注意咱们这里是对于任意节点K, 并不是特指他在数组哪个位置吧. 因此可以得出非常牛逼的结论:
    K3就是K1的最长公共前后缀的节点, 既然K3就是K1的最长公共前后缀的节点, 那么是否满足K == next[K]呢?
(6) 根据步骤(5), 既然找到的节点K3就是K1的最长公共前后缀的节点, 那么就可以直接通过K = next[K]获得K3的值。
复制代码